Hide-and-Seek in the House

Marin and Luka are playing a popular game of hide‐and‐seek inside a house. The house has n rooms, numbered 1 through n, and there are m doors, each connecting a pair of rooms. It is guaranteed that any two rooms are connected by a sequence of doors.

Luka has adopted a peculiar hiding strategy: for every room v, he has predetermined a room a_v in which he will hide whenever Marin enters room v. At the start of the game, Marin chooses a starting room v₀ and Luka hides in room a_v₀. In each round of the game, the following events occur in order:

1. Marin moves from her current room v to an adjacent room u (i.e. a room connected directly to v by a door).
2. Once Marin enters room u, Luka, knowing her move, goes to room a_u by any route he wishes (he may traverse any number of rooms in a single round).

The game ends at the moment when both players are in the same room. Note that this inevitably happens in a round if Marin enters a room u such that a_u = u (because Luka must end his move in u). Also, if the initial room satisfies v₀ = a_v₀, the game ends immediately before any rounds are played.

Marin has discovered Luka's strategy and now plans her moves optimally to catch him as quickly as possible, while Luka is assumed to choose his routes in a way that maximizes the number of rounds (i.e. delays capture as much as possible whenever it is inevitable). From Marin's perspective, the problem reduces to: for every starting room v, determine whether she can force a catch in a finite number of rounds and, if so, compute the minimum number of rounds required under optimal play by both sides.

Observation: The game essentially depends only on Marin’s moves since Luka’s final destination in each round is fixed by the function a. In particular, the catch will occur in a round when Marin moves to a room u for which \[ a_u = u. \] Such a room is called a trap room. Therefore, if Marin can reach any trap room from her starting room by moving along the doors, she can force a capture. The minimum number of rounds required is then simply the minimum number of moves (edges) needed to reach any trap room. If no trap room is reachable, the answer is -1.

The input guarantees that the house is connected, so if there exists at least one trap room then every room can reach a trap room. However, if no trap room exists then the answer for every starting room is -1.

Task: Given the structure of the house and the function a (i.e. the value a_i for each room), determine for every room v (considered as a starting room for Marin) the minimum number of rounds needed for Marin to catch Luka if both play optimally. Output -1 for those starting rooms from which a trap room is not reachable.

inputFormat

The input is given as follows:

• The first line contains two space‐separated integers n and m — the number of rooms and the number of doors.
• The second line contains n space‐separated integers: a₁, a₂, ..., aₙ, where a_i indicates the room where Luka hides when Marin enters room i.
• The following m lines each contain two space‐separated integers u and v, representing a door connecting room u and room v.

It is guaranteed that the house is connected (i.e. there is a path between any two rooms).

outputFormat

Output a single line with n space‐separated integers. The i-th integer should be the minimum number of rounds required for Marin to catch Luka when starting from room i, or -1 if it is impossible to do so.

sample

4 3
1 2 2 4
1 2
2 3
3 4

0 0 1 0