This year's Halloween will not be remembered for impressively carved pumpkins or wild parties. Unfortunately, we will remember it for the passing of Sean Connery, the famous Scottish actor who was the first to portray the character James Bond. Naturally, this news resonated around the world, and many celebrities said goodbye to this great man via social media. Pierce Brosnan stated that for him, Sean Connery is the best James Bond, and Josip Manolić joked a bit by saying that it is hardest for him when fellow spies leave us young. Interestingly, Mr. Malnar did not post on his Facebook profile, but instead immediately reached for a videotape of his favorite movie. Of course, it is the 1987 film The Untouchables, in which Sean Connery's character says the famous line – “Never bring a knife to a gunfight.”.

Mr. Malnar, due to his knife-throwing skills, has always been suspicious of this claim and decided to test its truth by placing targets on a tree in his yard. He quickly determined that the tree consists of $n$ nodes and decided to place one target in each node of the tree. He made the targets himself; they were circular, and one side of the target was painted green, while the other was red. After placing the targets in the nodes of the tree, he started throwing knives at them.

He soon noticed that he is infallible, meaning he will hit exactly the target he aimed at with perfect precision. Additionally, due to the force of the shot, that target will be completely destroyed, and the targets located at adjacent nodes to that target will rotate and, from Mr. Malnar's perspective, change color. Delighted by this fact, Mr. Malnar devised the following game:

• At the beginning of the game, there is a target in every node of the tree.
• Mr. Malnar may hit any of the targets that are, from his perspective, colored green with a single shot. According to the previous paragraph, the hit target will be destroyed, and its adjacent targets will change color.
• The goal of the game is to destroy all targets located on the tree.

Your task is to determine if Mr. Malnar can win this game. If he can, you must also determine any sequence of shots that will allow him to succeed.

Note: Two targets are adjacent if they are located in nodes that are directly connected by an edge.

Input

The first line contains a natural number $n$ ($1 \le n \le 200\,000$) from the problem description.

The second line contains $n$ space-separated numbers representing the colors of the targets located in the nodes of the tree. More precisely, the $i$-th number in the second line is $1$ if Mr. Malnar sees a green target in the $i$-th node, or $0$ if he sees a red target in that node.

The next $n - 1$ lines each contain two natural numbers $a$ and $b$ ($1 \le a, b \le n$) representing an edge between nodes $a$ and $b$. The edges are such that they form a tree, a simple connected graph without cycles.

Output

In the first line, print the word POBJEDA if Mr. Malnar can win the game, or PORAZ if he cannot.

In case a victory is possible, the second line must contain $n$ natural numbers that denote Mr. Malnar's shots in order. That is, the $i$-th printed number should represent the label of the node containing the target that Mr. Malnar will destroy with his $i$-th shot.

Examples

Input 1

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

Output 1

POBJEDA
2 1 3 5 4

Input 2

4
1 1 1 1
1 2
1 3
3 4

Output 2

PORAZ

Input 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

Output 3

POBJEDA
4 2 8 6 7 5 9 3 1