Задача F. Сильная связность ≡

Условие

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

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

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

Формат входного файла

В первой строке находится целое число n. Во второй строке находится целое неотрицательное число m₁. Далее в m₁ строках находятся описания ребер исходного графа. Каждое ребро задается номерами начала и конца. В следующей строке находится целое неотрицательное число m₂. Далее в m₂ строках находятся описания ребер, которые можно добавить. Каждое ребро задаётся номерами начала и конца и своим весом — целым числом от −10⁹ до 10⁹, включительно.

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 10⁵;

0 ≤ m₁ + m₂ ≤ 5dot 10⁵

Примеры тестов

2
1
1 2
1
2 1 40

YES
40
1
1

2
1
1 2
0

NO

4
5
1 2
1 3
2 3
2 4
3 4
2
4 2 1
3 1 1

YES
2
2
1 2