SPOJ 11414. Color over a tree

Seter 和 Fotile 在一棵包含 $N$ 个节点的树上进行游戏。树上的每个节点初始时为黑色或白色。两人轮流执行以下操作：

1. 在当前的树上选择一个白色节点；
2. 将从 $1$ 号节点到所选节点的路径上的所有节点涂成黑色。

当一名玩家无法进行操作，即树上不存在白色节点时，该玩家输掉游戏。

Seter 通过石头剪刀布获得了先手。已知双方都会采用最优策略，请判断 Seter 能否获胜；如果能够获胜，还需要找出所有能使他获胜的第一步选择。

输入格式

第一行包含一个正整数 $N$，表示树的节点数。

第二行包含 $N$ 个整数 $c_1,c_2,\ldots,c_N$，表示各节点的初始颜色。其中，$c_i=0$ 表示节点 $i$ 初始为白色，$c_i=1$ 表示节点 $i$ 初始为黑色。

接下来 $N-1$ 行，每行包含两个整数 $u,v$，表示树中节点 $u$ 与节点 $v$ 之间有一条边。

输出格式

如果双方均采用最优策略时 Seter 必败，输出一行 $-1$。

否则，按照节点编号从小到大的顺序，输出所有能使 Seter 获胜的第一步选择，每个节点编号单独占一行。

样例输入

8
1 1 0 1 0 0 1 0
1 2
1 3
2 6
3 4
3 5
5 7
7 8

样例输出

5

数据范围

• $1\le N\le 10^5$；
• $c_i\in\{0,1\}$。

来源与许可

本题题面与测试数据整理自 SPOJ 11414。

样例 1

输入

8
1 1 0 1 0 0 1 0
1 2
1 3
2 6
3 4
3 5
5 7
7 8

输出

5