Задача A. Дорожная реформа

Автор:XXII Городская олимпиада школьников Санкт-Петербурга по информатике   Ограничение времени:2 сек
Входной файл:roads.in   Ограничение памяти:1024 Мб
Выходной файл:roads.out  
Максимальный балл:120  

Условие

Как известно, Флатландское государство состоит из n городов, которые соединены системой двусторонних железнодорожных путей и автомобильных шоссе.

Недавно, после очередной поездки по стране, президент Флатландии остался крайне недовольным состоянием дорог и сделал вывод о необходимости радикальных реформ системы путей и сообщений.

Так как дорог в государстве за долгие годы было построено много, и почти все они нуждались в капитальном ремонте, то комиссией было решено, что необходимо закрыть часть существующих дорог, а на восстановление оставшихся выделить деньги из бюджета. При этом, так как средств в бюджете крайне не хватало, то было решено оставить как можно меньше железных и автомобильных дорог, лишь бы только по ним можно было добраться из любого города государства в любой другой (возможно через промежуточные города, используя несколько железных и/или автомобильных дорог), а именно, решено было оставить и отремонтировать ровно n − 1 дорогу.

После изучения результатов работы комиссии правительство решило выделить деньги на ремонт a автомобильных и b железных дорог. Но перед ним встала непростая задача: какие же конкретно дороги следует закрыть, а какие — оставить и отремонтировать, чтобы все города государства остались связанными друг с другом?

После тщетных попыток придумать план ремонта дорог, было решено обратиться к вам за помощью.

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

В первой строке входного файла записано четыре целых числа: n — количество городов Флатландии, m — количество существующих автомобильных и железных дорог, a и b — количество автомобильных и железных дорог, которые необходимо оставить. Следующие m строк описывают имеющиеся дороги. Каждая из них содержит по три целых числа: ui, vi — номера городов, которые соединяет i-я дорога, и ti — тип дороги, который равен 0 для автомобильной дороги, и 1 для железной.

Гарантируется, что ни один город не связан дорогой сам с собой, и что каждая пара городов соединена максимум одной автомобильной и одной железной дорогой. Также гарантируется, что перед реформой из каждого города можно добраться до каждого.

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

Если не существует плана ремонта дорог, удовлетворяющего описанным требованиям, то выведите в выходной файл единственное слово Impossible. Иначе выведите через пробел n − 1 число — номера дорог, которые необходимо отремонтировать (дороги нумеруются числами от 1 до m в порядке, в котором они заданы во входном файле). Если решений несколько, выведите любое.

Ограничения

1 ≤ n ≤ 100,000, n − 1 ≤ m ≤ 200,000, 0 ≤ a, b; a + b = n − 1, 1 ≤ ui, vi ≤ n

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

Входной файл (roads.in) Выходной файл (roads.out)
1
4 4 1 2
1 2 1
1 3 0
2 3 1
3 4 1
1 2 4
2
3 2 2 0
1 2 1
2 3 0
Impossible

0.108s 0.010s 13