Farmer John's new barn consists of N rooms (2 ≤ N ≤ 2500), consecutively numbered 1 x hellip; N, and N x minus; 1 corridors. Each corridor connects a pair of rooms in such a way that it is possible to go from one room to any through a series of corridors.
Each room in the barn has a round clock on the wall with the standard 1…12 on the front. However, this clock has only one hand, which always points exactly to one of the integers (it never points between two of those numbers).
Cow Besi wants to synchronize all the clocks in the barn so that they all point to the number 12. But with her cow thinking, every time she enters the room, she moves the hand forward one position. For example, if the arrow was pointing at 5, Besie will move the hand to 6. If the clock was pointing to 12, she will move the hand to 1. If Besie enters the room multiple times, she will move the hand each time she enters.
Determine the numbers of rooms in which Besie can start the journey through the barn to set all arrows to 12. Note that Besie does not move the arrow in the starting room at the beginning of the path and moves each time she enters it. The arrows themselves do not move. Besi entering the corridor must reach the end and enter the room at the end of the corridor. She can't turn back inside the hallway to re-enter the room she left.
Input
The first line of input contains N. The next line contains N integers, each in the range 1*12, indicating the initial positions of the arrows in each room. Each of the following N−1 lines describes a corridor with two integers a and b, each in the range 1…N, and the numbers of the rooms connected by this corridor.
Imprint
Print the numbers of the rooms Besi can start in to set all clocks to 12.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
4
11 10 11 11
12
2 3
24
|
1 |
In this example, Besi can only set all arrows to 12 if she starts in room 2 (e.g. moving like this: 1, 2, 3, 2, 4. |