| Codeforces Round 141 (Div. 2) |
|---|
| Закончено |
В Берляндии n городов, некоторые из которых соединены двунаправленными дорогами. Про каждую дорогу известно, заасфальтирована она, или нет.
Король Берляндии Валера II хочет заасфальтировать все дороги Берляндии, для этого он собрал бригаду рабочих. Каждый день Валера выбирает ровно один из городов и отдает приказ бригаде асфальтировать все дороги, исходящие из этого города. Доблестная бригада за день выполняет приказ короля, после чего работяги отправляются по домам.
К сожалению, не все так гладко, как хотелось бы Валере II. Основная часть бригады — гастарбайтеры. Поэтому, получив приказ заасфальтировать все дороги, исходящие из некоторого города, бригада асфальтировала все не асфальтированные дороги, исходящие из этого города, и, наоборот, снимала асфальт с тех дорог, где он был.
Узнав о таком ходе работ, Валера II был сильно расстроен, но так как менять что-либо было поздно, он попросил вас составить программу, которая бы определяла, можно ли хоть каким-то образом не более чем за n дней заасфальтировать все дороги Берляндии. Помогите королю.
В первой строке через пробел записаны два целых числа n, m 
— количество городов и дорог в Берляндии соответственно. В следующих m строках заданы описания дорог Берляндии: в i-й строке записаны три целых числа через пробел ai, bi, ci (1 ≤ ai, bi ≤ n; ai ≠ bi; 0 ≤ ci ≤ 1). Первые два числа (ai, bi) — номера городов, которые соединяет i-я дорога, третье число (ci) равно 1, если изначально дорога асфальтирована, и 0 в противном случае.
Считайте, что города в Берляндии пронумерованы от 1 до n, а дороги от 1 до m. Гарантируется, что между двумя городами Берляндии существует не более одной дороги.
В первой строке выведите единственное целое число x (0 ≤ x ≤ n) — количество дней, требуемое для ремонта всех дорог. Во второй строке через пробел выведите x целых чисел номера городов, в которые нужно посылать бригады, в том порядке, в котором Валера посылает их ремонтировать дороги. В случае, если решений несколько выведите любое.
Если заасфальтировать все дороги никак не получится, выведите «Impossible» (без кавычек).
4 4
1 2 1
2 4 0
4 3 1
3 2 0
4
3 2 1 3
3 3
1 2 0
2 3 0
3 1 0
Impossible
