Задача D. Робот

Автор:СПб 2005   Ограничение времени:2 сек
Входной файл:robot.in   Ограничение памяти:64 Мб
Выходной файл:robot.out  

Условие

В Пентагоне испытывают новый тип роботов. Испытания проводятся на полигоне, представляющем собой n комнат, соединенных цветными коридорами так, что между любыми двумя комнатами существует ровно один путь.

Для того, чтобы добраться от одной комнаты до другой, в робота вводится программа  — последовательность цветов коридоров c1, c2,… , ck, по которым он должен пройти.

Робот выбирает коридор цвета c1, ведущий из комнаты, в которой он находится, и идет по нему до следующей комнаты. В следующей комнате он рассматривает все коридоры, кроме того, по которому он пришел, выбирает из них коридор цвета c2 и идет по нему до третьей комнаты, в которой выбирает коридор цвета c3 и так далее. При этом, если есть более одного коридора требуемого цвета или нет ни одного такого коридора, то у робота происходит ошибка и он ломается.

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

Если, находясь в комнате 1, робот получит программу «2 2 3», то из комнаты 1 он сначала перейдет в комнату 3, затем в комнаты 5 и 6. Если же он получит программу «1 2 3» в комнате 4, то сначала он перейдет в комнату 3, а затем сломается, так как не сможет выбрать, по какому коридору ему идти дальше.

Ученые хотят построить центр управления в такой комнате, чтобы для любой другой комнаты A существовала корректная программа, получив которую, робот дойдет от центра управления до комнаты A.

Требуется написать программу, определяющую, в каких комнатах может находиться центр управления.

В приведенном примере центр управления может находиться в любой из комнат, кроме третьей и четвертой.

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

Первая строка входного файла содержит число n. Каждая из следующих n − 1 строк содержат по три числа: ai, bi, ci — описания коридоров, где ai и bi — номера комнат, соединяемых коридором, а ci — его цвет. Гарантируется что для любых двух комнат существует ровно один путь между ними.

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

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

Ограничения

1 &le; n &le; 105, 1&le; ai < bi&le; n, 1&le; ci&le; 105

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

Входной файл (robot.in) Выходной файл (robot.out)
1
6
1 3 2
5 6 3
3 4 1
1 2 1
3 5 2
1 2 5 6

0.081s 0.011s 17