Problem Description

Marin and Luka are playing a popular children's game, hide and seek, in their house. The house has \( n \) rooms connected by \( m \) pairs of doors. Rooms are numbered from 1 to \( n \), and there is a path connecting any two rooms.

Luka has devised a hiding strategy: when Marin enters room \( v \), Luka will hide in room \( a_v \). At the start of the game, Marin chooses the room \( v_0 \) to begin her search, and Luka hides in room \( a_{v_0} \). In each round of the game, Marin first selects an adjacent room \( u \) and enters it. Subsequently, knowing that Marin is in room \( u \), Luka will hide in room \( a_u \). Note that Luka can choose any route to reach room \( a_u \) and may pass through any number of rooms in one round.

The game ends when Marin and Luka are in the same room, which is defined as Marin finding Luka.

Marin has discovered Luka's hiding strategy and wants you to consider, for each starting room, whether she can find Luka within a finite number of rounds. If possible, calculate the minimum number of rounds required under ideal conditions (Marin minimizes the number of rounds, and Luka maximizes them).

Input Format

The first line contains two integers \( n \) and \( m \), representing the number of rooms and the number of pairs of connected rooms, respectively.

The second line contains \( n \) integers \( a_i \), representing Luka's hiding strategy.

The next \( m \) lines each contain two integers \( x_i \) and \( y_i \), indicating that these two rooms are connected. There is at most one direct path between any two rooms.

Output Format

A single line containing \( n \) numbers, representing the minimum number of rounds required. If the game cannot end in a finite number of steps, output \(-1\).

Sample Input and Output

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

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

Notes/Hints

[Sample Explanation #2]

In the first round, Marin moves from room 4 to room 8, and in the second round, she returns to room 4. Luka needs to pass through room 4 to move from room 7 to room 1. Therefore, Marin can find Luka in two rounds.

[Data Range]

For 100% of the data, \( 1 \leq n \leq 2 \times 10^5, n - 1 \leq m \leq \min(5 \times 10^5, \frac{n \times (n - 1)}{2}), 1 \leq a_i, x_i, y_i \leq n, x_i \neq y_i \).

This problem is worth 110 points.

见题面 Input 部分

见题面 Output 部分