eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Уникальный цвет

Уникальный цвет

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Дано дерево с n вершинами, пронумерованными от 1 до n. i - ое ребро соединяет вершину a_i и вершину b_i. Вершина i окрашена в цвет c_i (в этой задаче цвета представлены целыми числами).

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

Найдите все хорошие вершины.

Входные данные

Первая строка содержит количество вершин n~(2 \le n \le 10^5). Вторая строка содержит цвета c_1, c_2, ..., c_n~(1 \le c_i \le 10^5). Каждая из следующих n - 1 строк содержит два целых числа a_i и b_i~(1 \le a_i, b_i \le n).

Выходные данные

Выведите все хорошие вершины в виде целых чисел в порядке возрастания. Каждое число следует выводить в отдельной строке.

Пример

Входные данные #1
6
2 7 1 8 2 8
1 2
3 6
3 2
4 3
2 5
Выходные данные #1
1
2
3
4
6
Входные данные #2
10
3 1 4 1 5 9 2 6 5 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
Выходные данные #2
1
2
3
5
6
7
8