题目描述

给定一棵树，其 $N$ 个顶点的编号为 $1$ 到 $N$ 。第 $i$ 条边连接顶点 $A[i]$ 和顶点 $B[i]$ 。顶点 $i$ 的颜色为 $C[i]$ 。如果从顶点 $1$ 到顶点 $x$ 的路径上（最短路径），不包含与点 $x$ 相同颜色的点（顶点 $x$ 本身除外），我们称顶点 $x$ 为好点。按照升序输出所有好点。

输入格式

第一行输入一个正整数 $N$ ，表示顶点的数量。 第二行输入 $N$ 个正整数 $C[i]$ ，分别表示每个点的颜色。 之后 $N-1$ 行，每行输入两个正整数 $A[i],B[i]$ 表示一条树边。 其中 $2\le N\le 1e5$ ， $1\le C[i]\le 1e5$ ，保证给定的图是一棵树。

输出格式

输出使用换行符作为分隔符，按升序输出所有好点的编号。

数据范围

对于 $17\%$ 的数据， $2 \le N \le 10$ ；

对于 $33\%$ 的数据， $2 \le N \le 3000$ ；

对于 $100\%$ 的数据， $2 \le N \le 10^5, 1 \le C[i] \le 10^5, 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