P9760 [COCI 2022/2023 #3] Skrivača

Marin and Luka are playing a popular children's game—hide-and-seek—in their house. The house has $n$ rooms, and there are $m$ pairs of rooms connected by a door. The rooms are numbered from $1$ to $n$, and there is a path between every two rooms. Luka came up with 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$ where she starts searching, and Luka hides in room $a_{v_0}$. In each round of the game, Marin first chooses a room $u$ adjacent to her current room and enters it. Then Luka knows that Marin is in room $u$, so according to his hiding strategy he will hide in room $a_u$. Note that Luka may choose any route to reach room $a_u$, and in one round he may pass through any number of rooms. We say Marin finds Luka when both of them are in the same room; at that moment the game ends. Marin has discovered Luka's hiding strategy, so she wants you to determine, for each starting room, whether she can find Luka in a finite number of rounds. If she can, compute the minimum number of rounds needed under optimal play (Marin tries to minimize the number of rounds, Luka tries to maximize it).

The first line contains two integers $n,m$, representing the number of rooms and the number of connected pairs of rooms. The second line contains $n$ integers $a_i$, representing Luka's hiding strategy. In the next $m$ lines, each line contains two integers $x_i,y_i$, indicating that these two rooms are connected. There is at most one direct connection between any two rooms.

Output one line with $n$ numbers, representing the minimum number of rounds needed. If the game cannot end in a finite number of rounds, output $-1$.

**Sample Explanation #2.** In the first round, Marin goes from room $4$ to room $8$, and in the second round she goes back to room $4$. Luka must pass through room $4$ to get from room $7$ to room $1$. Therefore, Marin can find him in two rounds. **Constraints.** | Subtask | Points | Special Properties | | :----------: | :----------: | :----------: | | $1$ | $15$ | $n\le 1000,m\le2000$ | | $2$ | $25$ | $m=n-1$ | | $3$ | $30$ | Luka's hiding strategy satisfies that he will never hide in a room adjacent to or the same as Marin's current room, and the structure of the house satisfies that the game can end with at most $5$ different rooms, independent of Luka's hiding strategy. | | $4$ | $40$ | No special properties. | For $100\%$ of the testdata, $1\leq n \leq 2\times10^5$, $n-1\le m\le \min(5\times 10^5,\dfrac{n\times (n-1)}{2})$, $1\le a_i,x_i,y_i\le n$, $x_i\neq y_i$. The full score for this problem is $110$ points. Translated by ChatGPT 5