eolymp
bolt
Try our new interface for solving problems
Məsələlər

Сильно связанный сын гор

Сильно связанный сын гор

Zaman məhdudiyyəti 5 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Эльдар Богданов, как и надлежит славному сыну гор - сильный мужчина, но в то же время он связан взятыми на себя обязательствами перед Иваном Метельским провести свой день на Зимней Школе 2011 на высоком уровне. Более того, одним из пунктов излагаемого им теоретического материала были компоненты сильной связности, а тут ещё в жизни такой компонентой неожиданно оказался Снарк, предложивший провести "Гран-При Двух Столиц", что ещё больше связывало Эльдара.

Однако он от такой связности Эльдар не становился менее сильным, а наоборот, он всё более сильно вникал в решение следующей задачки:

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

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

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

  • суммарный вес добавленных рёбер должен быть минимальным.

Пока Эльдар сильно занят связями с Иваном, Снарком и предстоящим на тот момент проведением Гран-При Двух Столиц, он предложил решить эту задачку Вам, и в любом случае сообщить ему о наличии решения сформулированной задачи, а в случае наличия решения - посчитать и кое-что ещё...

Giriş verilənləri

В первой строке находится целое число n (1n100000). Во второй строке находится целое неотрицательное число m_1. Далее в m_1 строках находятся описания ребер исходного графа. Каждое ребро задается номерами начала и конца. В следующей строке находится целое неотрицательное число m_2. Далее в m_2 строках находятся описания ребер, которые можно добавить. Каждое ребро задаётся номерами начала и конца и своим весом - целым числом от -10^9 до 10^9, включительно. Известно, что 0m_1 + m_2500000.

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
2
1
1 2
1
2 1 40
Çıxış verilənləri #1
YES
40
1
1