Marin and Luka are playing a popular kids' game called Hide and Seek (Skrivača). They are playing in their house, which has rooms, and pairs of rooms are connected by a door. Rooms are labelled from to and for each pair of rooms there exists a path from one room to another.
Luka has thought of a hiding strategy: when Marin enters room , Luka will hide in room . At the start of the game, Marin chooses his starting room , and Luka hides in room . In each step of the game, firstly, Marin chooses a room adjacent to his current room and enters it. After that, Luka knows Marin is in room , so by his hiding strategy, he hides in room . Notice that Luka can choose any path to reach room and that in one step of the game, he can pass through an arbitrary number of rooms.
Marin will find Luka when both of them are located in the same room, and at that moment, the game ends.
Marin found out about Luka's hiding strategy, so he wants you to determine for each starting room if Marin can find Luka in a finite amount of steps and, if he can, determine the least amount of steps necessary if both of them play optimally. (Marin plays such that he finds Luka in the least amount of steps, and Luka plays such that Marin finds him in the most amount of steps).
In the first line, there are integers , , the number of rooms and the number of pairs of connected rooms.
In the second line, there are integers , describing Luka's hiding strategy.
In -th of the next lines there are integers , , denoting that room and room are connected. Between each pair of rooms, there will be at most one connection.
In the first and only line, print numbers, where the -th number represents the least amount of steps
necessary for Marin to find Luka if Marin starts in room , or
-1 if Marin can't find Luka.
|Luka's hiding strategy will be such that he will never attempt to hide in the same or adjacent room to where Marin is currently located, and the structure of the house will be such that the game can end in at most different rooms independent of Luka's hiding strategy.|
|No additional constraints.|
Sample Input 1
4 4 3 4 1 2 1 2 2 3 3 4 4 1
Sample Output 1
-1 -1 -1 -1
Sample Input 2
8 9 2 3 2 1 6 5 6 7 1 2 1 3 2 4 3 4 4 5 4 6 6 7 5 7 4 8
Sample Output 2
1 2 2 2 1 1 1 1
Explanation for Sample 2
Marin enters room from room in the first step, and in the second, he goes back to room . Luka needs to pass through room to get from room to room so Marin can find Luka in steps.
Sample Input 3
9 8 1 9 1 1 1 9 9 9 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9
Sample Output 3
0 1 1 2 1 1 2 1 1