Malnar 先生因其投掷飞刀的技巧，一直对“不要在枪战中带刀”这一说法持怀疑态度，并决定通过在院子里的树上放置靶子来验证其真实性。他很快确定这棵树由 $n$ 个节点组成，并决定在树的每个节点上放置一个靶子。他亲手制作了这些靶子，它们呈圆形，一面涂成绿色，另一面涂成红色。在将靶子放置在树的节点上后，他开始用飞刀投掷它们。

他很快发现自己百发百中，即他能以完美的精度击中他所瞄准的那个靶子。此外，由于投掷的力度，该靶子会被完全摧毁，而位于该靶子相邻节点上的靶子会翻转，从 Malnar 先生的角度来看，它们的颜色会发生改变。受此启发，Malnar 先生设计了以下游戏：

• 游戏开始时，树的每个节点上都有一个靶子。
• Malnar 先生每次投掷可以击中任何一个从他视角看是绿色的靶子。根据前文所述，被击中的靶子将被摧毁，与其相邻的靶子将改变颜色。
• 游戏的目标是摧毁树上的所有靶子。

你的任务是确定 Malnar 先生是否能在该游戏中获胜。如果可以，还需要确定他获胜所需的任何一种投掷顺序。

注：如果两个靶子所在的节点通过一条边直接相连，则称这两个靶子相邻。

输入格式

第一行包含一个自然数 $n$ ($1 \le n \le 200\,000$)。

第二行包含 $n$ 个用空格分隔的数字，表示树中节点上靶子的颜色。具体来说，如果第 $i$ 个数字为 $1$，则表示 Malnar 先生在第 $i$ 个节点看到的是绿色靶子；如果为 $0$，则表示他看到的是红色靶子。

接下来的 $n - 1$ 行，每行包含两个自然数 $a$ 和 $b$ ($1 \le a, b \le n$)，表示节点 $a$ 和 $b$ 之间的一条边。这些边构成了一棵树，即一个无环的简单连通图。

输出格式

第一行输出单词 POBJEDA（表示 Malnar 先生可以获胜），如果不能获胜，则输出 PORAZ。

如果获胜是可能的，第二行需要输出 $n$ 个自然数，依次表示 Malnar 先生的投掷顺序。即第 $i$ 个输出的数字应表示 Malnar 先生第 $i$ 次投掷所摧毁的靶子所在的节点编号。

样例

样例输入 1

5
0 1 0 1 1
1 2
2 3
3 4
4 5

样例输出 1

POBJEDA
2 1 3 5 4

样例输入 2

4
1 1 1 1
1 2
1 3
3 4

样例输出 2

PORAZ

样例输入 3

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

样例输出 3

POBJEDA
4 2 8 6 7 5 9 3 1