Skrivača

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 labeled from $1$ to $n$, and for each pair of rooms there exists a path from one room to another.

Luka has chosen 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, Marin first 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$. Luka can choose any path to reach room $a_u$, and in one step of the game he can pass through an arbitrary number of rooms.

Marin finds Luka when both of them are in the same room, and at that moment the game ends.

Marin knows Luka's hiding strategy. For each starting room, determine whether Marin can find Luka in a finite number of steps, and if he can, the least number of steps needed if both play optimally. Marin plays so that he finds Luka in as few steps as possible, and Luka plays so that Marin needs as many steps as possible.

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(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 the $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. Each pair of rooms has at most one connection.

Print $n$ numbers in the first and only line. The $i$-th number is the least number of steps Marin needs to find Luka if Marin starts in room $i$, or $-1$ if Marin cannot find Luka.

Clarification of the second example: Marin enters room 8 from room 4 in the first step, and in the second step 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.