Marin and Luka are playing a popular kids' game called Hide and Seek (Skrivača). They are playing in their house, which has $n$ rooms, and $m$ pairs of rooms are connected by a door. Rooms are labelled from $1$ to $n$ 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 $v$, Luka will hide in room $a_v$. At the start of the game, Marin chooses his starting room $v_0$, and Luka hides in room $a_{v_0}$. In each step of the game, firstly, Marin chooses a room $u$ adjacent to his current room and enters it. After that, Luka knows Marin is in room $u$, so by his hiding strategy, he hides in room $a_u$. Notice that Luka can choose any path to reach room $a_u$ 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).

Input Specification

In the first line, there are integers $n$, $m$ $(1\le n\le 2\cdot {10}^5,n-1\le m\le min(5\cdot {10}^5,\frac{n\cdot (n-1)}{2})$, the number of rooms and the number of pairs of connected rooms.

In the second line, there are $n$ integers $a_i$ $(1\le a_i\le n)$, describing Luka's hiding strategy.

In $i$-th of the next $m$ lines there are integers $x_i$, $y_i$ $(1\le x_i,y_i\le n,x_i\ne y_i)$, denoting that room $x_i$ and room $y_i$ are connected. Between each pair of rooms, there will be at most one connection.

Output Specification

In the first and only line, print $n$ numbers, where the $i$-th number represents the least amount of steps necessary for Marin to find Luka if Marin starts in room $i$, or -1 if Marin can't find Luka.

Constraints

Subtask	Points	Constraints
$1$	$15$	$n\le 1000$, $m\le 2000$
$2$	$25$	$m=n-1$
$3$	$30$	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 $5$ different rooms independent of Luka's hiding strategy.
$4$	$40$	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 $8$ from room $4$ in the first step, and in the second, he goes back to room $4$. Luka needs to pass through room $4$ to get from room $7$ to room $1$ so Marin can find Luka in $2$ 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