You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

一棵 n 个节点的树，编号为 1 到 ​n​。每个节点上都有若干个石子。

小 A 和小 B 要利用这棵树进行一场比赛，比赛规则如下：

1.由小 A 选择一个点 s ，在上面放一个装石子的盒子，然后从小 A 开始，两人开始轮流拿取石子；

2.双方每次都必须先从盒子所在的节点拿取一个石子，然后将盒子移动到一个相邻节点上，之后对方再拿石子，以此往复；

3.如果谁能够将盒子移动到没有石子的节点上则获胜。

双方都足够聪明，问小 A 可以选择哪些节点，让自己获胜。

输入格式

第一行输入一个正整数n，表示节点数量。 第二行输入n个整数w[i]，分别表示每个节点上的石子数量。 之后n-1行，每行输入两个正整数u,v，表示点u,v间有一条边。 其中2≤n≤3000，0≤w[i]≤10​^9^。

输出格式

输出仅一行，按照编号的升序，输出可以让小A获胜的节点。如果小A一定无法获胜，输出-1。

输入样例

3
1 2 3
1 2
2 3​

输出样例

2

数据范围

对于13%的数据，2≤​n​≤5；

对于17%的数据，2≤​n​≤1000；

对于100%的数据，2≤​n​≤3000,1≤​u​,​v​≤​n​, 0<=w[i] <=10^9。