В городе, где живет Валера, скоро состоятся выборы в Городскую Думу.
Всего в городе есть n районов и n - 1 двусторонняя дорога. При этом известно, что из любого района существует путь по дорогам в любой другой район. Пронумеруем все районы в городе некоторым образом целыми числами от 1 до n включительно. Для каждой дороги жители определили, является ли она проблемной или нет. Проблемная дорога — это дорога, которая нуждается в ремонте.
На выборы баллотируются n кандидатов. Пронумеруем всех кандидатов некоторым образом целыми числами от 1 до n включительно. Если кандидат с номером i будет избран в Городскую Думу, то он выполнит ровно одно обещание — отремонтировать все проблемные дороги на пути от района с номером i до района с номером 1, в котором расположена Городская Дума.
Помогите Валере и найдите множество кандидатов, после избрания которых в Городскую Думу все проблемные дороги в городе будут отремонтированы. Если же существует несколько таких множеств, следует выбрать множество, состоящее из минимального количества кандидатов.
Выходные данные
В первой строке выведите одно целое неотрицательное число k — минимальный возможный размер искомого множества.
Во второй строке выведите k целых чисел a1, a2, ... ak — номера кандидатов, которые образуют искомое множество. Если существует несколько решений, то разрешается вывести любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 2
2 3 2
3 4 2
4 5 2
|
1
5
|
|
2
|
5
1 2 1
2 3 2
2 4 1
4 5 1
|
1
3
|
|
3
|
5
1 2 2
1 3 2
1 4 2
1 5 2
|
4
5 4 3 2
|