Задача: Часовое дерево
Новый амбар Фермера Джона состоит из N комнат (2 ≤ N ≤ 2500), последовательно пронумерованных 1…N, и N−1 коридоров. Каждый коридор соединяет пару комнат таким образом, что возможно пройти из лбой комнаты в любую через серию коридоров.
Каждая комната в амбаре имеет круглые часы на стене со стандартным размещением цифр 1…12 на лицевой стороне. Однако на этих часах имеется только одна стрелка, которая всегда показывает точно на одно из целых чисел (она никогда не показывает между двумя из этих чисел).
Корова Беси хочет синхронизировать все часы в амбаре, чтобы они все показывали на число 12. Но со своим коровьим мышлением, каждый раз, когда она входит в комнату, она перемещает стрелку вперёд на одну позицию. Например, если стрека показывала на 5, Беси переводит стрелку на 6. Если часы указывали на 12, она переводит стрелку на 1. Если Беси входит в комнату несколько раз, она переводит стрелку при каждом входе.
Определите номера комнат, в которых Беси может начинать путешествие по амбару чтобы установить все стрелки на 12. Заметим, что Беси не переводит стрелку в стартовой комнате в начале пути и переводит при каждом последующем входе в неё. Стрелки сами по себе не двигаются. Беси входя в коридор должна дойти до конца и войти в комнату в конце коридора. Она не может повернуть назад внутри коридора, чтобы снова войти в комнату из которой вышла.
Входные данные
Первая строка ввода содержит N. Следующая строка содержит N целых чисел, каждое в интервале 1…12, указывающих начальные положения стрелок в каждой комнате. Каждая из следующих N−1 строк описывает коридор двумя целыми числам a и b, каждое в интервале 1…N, и задающих номера комнат, соединённых этим коридором.
Выходные данные
Выведите номера комнат, в которых Беси может начинать, чтобы установить все часы на 12.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
4
11 10 11 11
1 2
2 3
2 4
|
1 |
В этом примере Беси может установить все стрелки на 12, тоько в том случае, если она начнёт в комнате 2 (например перемещаясь так: 1, 2, 3, 2, 4. |
Ваш ответ: