Description
Seter和Fotile在一棵N个点的树上玩游戏。这棵树的每个点不是黑色的就是白色的。
他们轮流进行以下操作:
在当前的树上选择一个白色节点;
把1号点到选择节点的路径上所有点涂黑。
Seter或Fotile输掉游戏当且仅当无法操作(没有白色节点)。
Seter用石头剪刀布获得了先手机会,但是他知道Fotile很聪明,会按照最优策略选点
他想知道自己有没有可能赢得游戏,否则他就要掀桌了。
Input
第一行包含一个正整数N表示树的节点数。 1<=n<=100000
第二行包括N个0或1:c1,c2,..cn。
ci=0 表示第i个点一开始是白色的而 ci=1 表示黑色。
接下来N-1行每行两个整数u,v描述整棵树。
Output
如果Seter输定了或者你也不会做,输出-1让他掀桌.
否则按照增序输出所有Seter第一步可以选择的点,使得Seter能获胜。
Sample Input
Input#1:8
1 1 0 1 0 0 1 0
1 2
1 3
2 6
3 4
3 5
5 7
7 8
Input#2:
20
1 1 1 0 1 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0
1 2
2 3
2 4
1 5
1 6
5 7
5 8
2 9
8 10
1 11
1 12
9 13
6 14
14 15
7 16
11 17
2 18
7 19
12 20
Sample Output
Output#1:5
Output#2
8
11
12