Codeforces Round 216 (Div. 2) |
---|
Закончено |
В городе, где живет Валера, скоро состоятся выборы в Городскую Думу.
Всего в городе есть n районов и n - 1 двусторонняя дорога. При этом известно, что из любого района существует путь по дорогам в любой другой район. Пронумеруем все районы в городе некоторым образом целыми числами от 1 до n включительно. Для каждой дороги жители определили, является ли она проблемной или нет. Проблемная дорога — это дорога, которая нуждается в ремонте.
На выборы баллотируются n кандидатов. Пронумеруем всех кандидатов некоторым образом целыми числами от 1 до n включительно. Если кандидат с номером i будет избран в Городскую Думу, то он выполнит ровно одно обещание — отремонтировать все проблемные дороги на пути от района с номером i до района с номером 1, в котором расположена Городская Дума.
Помогите Валере и найдите множество кандидатов, после избрания которых в Городскую Думу все проблемные дороги в городе будут отремонтированы. Если же существует несколько таких множеств, следует выбрать множество, состоящее из минимального количества кандидатов.
В первой строке задано одно целое число n (2 ≤ n ≤ 105) — количество районов в городе.
Далее следует n - 1 строка. Каждая строка содержит описание дороги в виде трех целых положительных чисел xi, yi, ti (1 ≤ xi, yi ≤ n, 1 ≤ ti ≤ 2) — районы, которые соединяет i-я двусторонняя дорога, и тип дороги. Если ti равно единице, то i-я дорога не является проблемной; если ti равно двум, то i-я дорога является проблемной.
Гарантируется, что если представить город в виде графа дорог, граф будет являться деревом.
В первой строке выведите одно целое неотрицательное число k — минимальный возможный размер искомого множества.
Во второй строке выведите k целых чисел a1, a2, ... ak — номера кандидатов, которые образуют искомое множество. Если существует несколько решений, то разрешается вывести любое.
5
1 2 2
2 3 2
3 4 2
4 5 2
1
5
5
1 2 1
2 3 2
2 4 1
4 5 1
1
3
5
1 2 2
1 3 2
1 4 2
1 5 2
4
5 4 3 2
Название |
---|