Skrivača

마린과 루카는 숨바꼭질(Skrivača)이라는 인기 있는 어린이 게임을 하고 있다. 그들은 방이 $n$개 있는 집에서 놀고 있으며, $m$쌍의 방이 문으로 연결되어 있다. 방은 1번부터 $n$번까지 번호가 매겨져 있고, 임의의 두 방 사이에는 경로가 존재한다.

루카는 숨는 전략을 정했다. 마린이 방 $v$에 들어가면 루카는 방 $a_v$에 숨는다. 게임 시작 시 마린은 시작 방 $v_0$을 고르고, 루카는 방 $a_{v_0}$에 숨는다. 매 단계에서 마린은 먼저 현재 방과 인접한 방 $u$를 골라 들어간다. 그러면 루카는 마린이 방 $u$에 있다는 것을 알고, 숨는 전략에 따라 방 $a_u$에 숨는다. 루카는 방 $a_u$에 도달하는 경로를 임의로 택할 수 있고, 한 단계에서 방을 몇 개든 지나갈 수 있다.

두 사람이 같은 방에 있게 되면 마린이 루카를 찾은 것이며, 그 순간 게임이 끝난다.

마린은 루카의 숨는 전략을 알고 있다. 각 시작 방에 대해, 마린이 유한한 단계 안에 루카를 찾을 수 있는지 판단하라. 찾을 수 있다면 두 사람이 최적으로 행동할 때 필요한 최소 단계 수를 구하라. 마린은 가능한 한 적은 단계에 루카를 찾도록 행동하고, 루카는 마린이 가능한 한 많은 단계를 쓰도록 행동한다.

첫 줄에 정수 $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})$)이 주어진다. 방의 개수와 연결된 방 쌍의 개수이다.

둘째 줄에 루카의 숨는 전략을 나타내는 $n$개의 정수 $a_i$ ($1 \le a_i \le n$)가 주어진다.

이어지는 $m$개의 줄 중 $i$번째 줄에는 정수 $x_i$, $y_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$)가 주어지며, 방 $x_i$와 방 $y_i$가 연결되어 있음을 뜻한다. 같은 방 쌍을 잇는 연결은 최대 하나이다.

첫 줄에 $n$개의 수를 출력한다. $i$번째 수는 마린이 방 $i$에서 시작할 때 루카를 찾기까지 필요한 최소 단계 수이며, 찾을 수 없다면 $-1$을 출력한다.

두 번째 입력 예제에 대한 설명이다. 마린은 첫 단계에서 방 4에서 방 8로 들어가고, 두 번째 단계에서 방 4로 돌아온다. 루카는 방 7에서 방 1로 가려면 방 4를 지나야 하므로, 마린은 2단계 만에 루카를 찾을 수 있다.