eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Міцно зв`язаний син гір

Міцно зв`язаний син гір

Ліміт часу 5 секунд
Ліміт використання пам'яті 256 MiB

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

Проте від такої зв'язаності Ельдар не ставав менш сильним, а навпаки, він все більш сильно вникав у розв'язання наступної задачки:

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

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

  • граф з доданими ребрами повинен бути сильно зв'язним (кожна вершина повинна бути досяжною з кожної),

  • сумарна вага доданих ребер повинна бути мінімальною.

Поки Ельдар сильно зайнятий зв'язками з Іваном, Снарком і майбутнійм на той момент проведенням Гран-Прі Двох Столиць, він запроронував розв'язати цю задачку Вам, і у довільному випадку повідоміти йому про наявність розв'язку сформульованої задачі, а у випадку наявності розв'язку - прахувати і ще дещо...

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #1
2
1
1 2
1
2 1 40
Вихідні дані #1
YES
40
1
1