Автор: | XXII Городская олимпиада школьников Санкт-Петербурга по информатике | Ограничение времени: | 2 сек | |
Входной файл: | roads.in | Ограничение памяти: | 1024 Мб | |
Выходной файл: | roads.out | |||
Максимальный балл: | 120 |
Как известно, Флатландское государство состоит из n городов, которые соединены системой двусторонних железнодорожных путей и автомобильных шоссе.
Недавно, после очередной поездки по стране, президент Флатландии остался крайне недовольным состоянием дорог и сделал вывод о необходимости радикальных реформ системы путей и сообщений.
Так как дорог в государстве за долгие годы было построено много, и почти все они нуждались в капитальном ремонте, то комиссией было решено, что необходимо закрыть часть существующих дорог, а на восстановление оставшихся выделить деньги из бюджета. При этом, так как средств в бюджете крайне не хватало, то было решено оставить как можно меньше железных и автомобильных дорог, лишь бы только по ним можно было добраться из любого города государства в любой другой (возможно через промежуточные города, используя несколько железных и/или автомобильных дорог), а именно, решено было оставить и отремонтировать ровно n − 1 дорогу.
После изучения результатов работы комиссии правительство решило выделить деньги на ремонт a автомобильных и b железных дорог. Но перед ним встала непростая задача: какие же конкретно дороги следует закрыть, а какие — оставить и отремонтировать, чтобы все города государства остались связанными друг с другом?
После тщетных попыток придумать план ремонта дорог, было решено обратиться к вам за помощью.
В первой строке входного файла записано четыре целых числа: n — количество городов Флатландии, m — количество существующих автомобильных и железных дорог, a и b — количество автомобильных и железных дорог, которые необходимо оставить. Следующие m строк описывают имеющиеся дороги. Каждая из них содержит по три целых числа: ui, vi — номера городов, которые соединяет i-я дорога, и ti — тип дороги, который равен 0 для автомобильной дороги, и 1 для железной.
Гарантируется, что ни один город не связан дорогой сам с собой, и что каждая пара городов соединена максимум одной автомобильной и одной железной дорогой. Также гарантируется, что перед реформой из каждого города можно добраться до каждого.
№ | Входной файл (roads.in ) |
Выходной файл (roads.out ) |
---|---|---|
1 |
|
|
2 |
|
|