题目描述

译自 COCI 2022/2023 Contest #3 T5「Skrivača」

Marin 和 Luka 正在家中玩捉迷藏（Skrivača）。家里共有 $n$ 个房间，有 $m$ 对放假通过一扇门连接起来。房间编号为 $1$ 到 $n$，并且对于每个房间，都存在一条从一个房间到另一个房间的路径。

Luka 想到了一个藏身方案：当 Marin 进入房间 $v$ 时，Luka 会躲在房间 $a_v$。在开始时 Marin 选择他开始的房间 $v_0$，然后 Luka 躲在房间 $a_{v_0}$。对于游戏中的每一轮，首先 Marin 选择一个与目前所处的房间相邻的房间 $u$ 并进入。在这之后，Luka 知道 Marin 在房间 $u$，所以根据藏身方案，他会藏在房间 $a_u$。注意 Luka 可以选择任意路径到达 $a_u$，在这一轮中他可以经过任意数量的房间。

当 Marin 和 Luka 位于同一房间时，Marin 就会发现 Luka，在那一时刻游戏结束。

Marin 发现了 Luka 的藏身策略，所以他希望你能确定对于每个开始房间，Marin 是否可以在有限轮中找到 Luka，并且如果他可以，确定当双方均以最佳策略（Marin 按照他尽可能在最少轮数找到 Luka 的目标进行游戏，Luka 按照他尽可能在最多轮数被 Marin 发现的目标进行游戏）进行游戏时 Marin 找到 Luka 的最小轮数。

输入格式

第一行两个整数 $n,m\ (1\le n\le 2\cdot 10^5,n-1\le m\le \min(5\cdot 10^5,\frac{n\cdot (n-1)}{2}))$，表示房间数和门数。

第二行 $n$ 个整数 $a_i\ (1\le a_i\le n)$，表示 Luka 的藏身策略。

接下来 $m$ 行，每行两个整数 $x_i,y_i\ (1\le x_i,y_i\le n,x_i\neq y_i)$，表示房间 $x_i$ 和 $y_i$ 之间有一扇门相连。在任意一对房间之间最多只有一扇门。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示 Marin 在房间 $i$ 开始游戏时找到 Luka 所需的最小轮数。如果 Marin 找不到 Luka，输出 $-1$。

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

-1 -1 -1 -1

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

1 2 2 2 1 1 1 1

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

0 1 1 2 1 1 2 1 1

数据范围与提示

详细子任务附加限制及分值如下表所示。