题目描述

Marin 和 Luka 正在他们的房子里玩一个流行的儿童游戏——捉迷藏。这个房子共有 $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 的躲藏策略，所以她想要你考虑从每一个房间出发时，她是否可以在有限回合找到 Luka。如果可以，计算在理想状态下（Marin 尽可能减少回合数，Luka 尽可能增加回合数）最少需要的回合数。

输入格式

第一行两个整数 $n,m$，分别表示房间的数量和相连房间的对数。

第二行 $n$ 个整数 $a_i$，表示 Luka 的躲藏策略。

在接下来的 $m$ 行中，每行两个整数 $x_i,y_i$，表示这两个房间是相连的。任意两个房间最多只有一条直接相连的道路。

输出格式

一行 $n$ 个数，表示最少需要的回合数。如果无法在有限步中结束游戏，输出 $-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

提示

【样例解释 #2】

Marin 第一回合从房间 $4$ 进入房间 $8$，第二回合回到房间 $4$。Luka 需要经过房间 $4$ 才能从房间 $7$ 到房间 $1$。所以可以在两个回合找到。

【数据范围】

对于 $100\%$ 的数据，满足 $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$。

本题满分 $110$ 分。