АВТ ВоГУ - Задача 1593. Сильная связность

Задан ориентированный граф из n вершин и m₁ рёбер. Известно, что в графе есть вершины s и t такие, что все вершины достижимы из s, и из всех вершин достижима t. Также на том же множестве вершин задано другое множество рёбер, состоящее из m₂ элементов. Рёбрам из этого множества приписаны некоторые целые веса.

Вам необходимо добавить к графу некоторые рёбра из второго множества так, чтобы выполнялись следующие требования:

граф с добавленными рёбрами должен быть сильно связным (каждая вершина должна быть достижима из каждой),
суммарный вес добавленных рёбер должен быть минимальным.

Входные данные

В первой строке находится целое число n (1 ≤ n ≤ 100 000). Во второй строке находится целое неотрицательное число m₁. Далее в m₁ строках находятся описания ребер исходного графа. Каждое ребро задается номерами начала и конца. В следующей строке находится целое неотрицательное число m₂. Далее в m₂ строках находятся описания ребер, которые можно добавить. Каждое ребро задаётся номерами начала и конца и своим весом — целым числом от - 10⁹ до 10⁹, включительно. Известно, что 0 ≤ m₁ + m₂ ≤ 500 000.

Выходные данные

В первую строку выведите «YES» или «NO» в зависимости от того, существует ли решение задачи. Если решение существует, выведите три строки. В первой из них вывeдите суммарный вес добавленных рёбер. Во второй выведите количество добавленных рёбер. В третьей через пробел выведите номера добавленных рёбер. Рёбра нумеруются с единицы в том порядке, в котором они перечислены во входном файле. Каждое добавленное ребро нужно выводить ровно один раз.

Примеры

Входные данные

Выходные данные

YES
40
1
1

Входные данные

Выходные данные

NO

Входные данные

Выходные данные

YES
2
2
1 2

Дистанционный практикум по программированию

1593. Сильная связность