eolymp
bolt
Try our new interface for solving problems
Problems

Unique Color

Unique Color

Time limit 1 second
Memory limit 128 MiB

Given a tree with n vertices numbered 1 through n. The i-th edge connects Vertex a_i and Vertex b_i. Vertex i is painted in color c_i (in this problem, colors are represented as integers).

Vertex x is said to be good when the shortest path from Vertex 1 to Vertex x does not contain a vertex painted in the same color as Vertex x, except for Vertex x itself.

Find all the good vertices.

Input data

The first line contains the number of vertices n~(2 \le n \le 10^5). The second line contains colors c_1, c_2, ..., c_n~(1 \le c_i \le 10^5). Each of the next n - 1 lines contains two integers a_i and b_i~(1 \le a_i, b_i \le n).

Output data

Print all good vertices as integers, in ascending order. Print each number on a separate line.

Examples

Input example #1
6
2 7 1 8 2 8
1 2
3 6
3 2
4 3
2 5
Output example #1
1
2
3
4
6
Input example #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
Output example #2
1
2
3
5
6
7
8