Задача 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 ≤ n ≤ 105, 1≤ ai < bi≤ n, 1≤ ci≤ 105Примеры тестов
| № | Входной файл (robot.in) |
Выходной файл (robot.out) |
|---|---|---|
| 1 | |
|