Транспортная реформа
(Время: 1 сек. Память: 32 Мб Сложность: 70%)
Далекое королевство состоит из n городов, соединенных m дорогами, при этом из каждого города можно доехать в каждый по дорогам (по каждой из дорог можно ездить в обоих направлениях). Некоторые дороги находятся в хорошем состоянии, другие же требуют ремонта.
Содержание каждой из дорог обходится казне в 239239 дублонов в год. В связи с новой транспортной реформой, направленной на уменьшение ненужных расходов, было решено оставить на государственном содержании как можно меньше дорог, но по-прежнему должна остаться возможность из каждого города добраться в любой другой по государственным дорогам. Заметим, что при этом на государственном содержании останется ровно n - 1 дорога.
При этом, возможно, в число оставленных дорог войдут и требующие ремонта. Сэкономленные в связи с этой реформой деньги планируется направить на ремонт дорог, оставленных на государственном содержании.
В королевстве есть две конкурирующие фирмы, занимающиеся починкой дорог. Поскольку король не желает быть обвиненным в поддержке одной из этих фирм, он хочет иметь возможность распределить дороги, оставленные на государственном содержании и требующие ремонта, поровну между ними. В связи с этим требуется оставить на государственном содержании четное число дорог, требующих ремонта.
Требуется составить соответствующий желанию короля список дорог, которые следует оставить на государственном содержании.
Входные данные
Первая строка входного файла INPUT.TXT содержит натуральные числа n (2 ≤ n ≤ 30 000) и m (1 ≤ m ≤ 100 000) - число городов и дорог в королевстве соответственно. Далее идут m строк - описание дорог. Дорога описывается тремя числами. Первые два из них - номера городов, которые она соединяет, третье равно 1, если дорога не требует ремонта, и 2, если требует. Города пронумерованы целыми числами от 1 до n. Ни одна дорога не соединяет город с самим собой, между любыми двумя городами не более одной дороги.
Выходные данные
В выходной файл OUTPUT.TXT выведите n-1 строку - номера государственных дорог (дороги нумеруются с 1 в том порядке, в котором они идут во входном файле). Если оставить на государственном содержании дороги указанным образом невозможно, то следует вывести -1.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 4
1 2 1
2 3 2
3 4 1
4 1 2 | 2
3
4 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
