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 尽可能增加回合数）最少需要的回合数。
## Input
第一行两个整数 $n,m$，分别表示房间的数量和相连房间的对数。
第二行 $n$ 个整数 $a_i$，表示 Luka 的躲藏策略。
在接下来的 $m$ 行中，每行两个整数 $x_i,y_i$，表示这两个房间是相连的。任意两个房间最多只有一条直接相连的道路。
## Output
一行 $n$ 个数，表示最少需要的回合数。如果无法在有限步中结束游戏，输出 $-1$。
[samples]
## Note
**【样例解释 #2】**
Marin 第一回合从房间 $4$ 进入房间 $8$，第二回合回到房间 $4$。Luka 需要经过房间 $4$ 才能从房间 $7$ 到房间 $1$。所以可以在两个回合找到。
**【数据范围】**
| 子任务 | 分值 | 特殊性质 |
| :----------: | :----------: | :----------: |
| $1$ | $15$ | $n\le 1000,m\le2000$ |
| $2$ | $25$ | $m=n-1$ |
|$3$ | $30$| Luka 的躲藏策略满足他永远不会躲在与 Marin 当前所在房间相邻或相同的房间，并且房子的结构满足游戏可以在最多有 $5$ 个不同房间独立于 Luka 的躲藏策略之外的情况下结束游戏。
| $4$ | $40$ | 无特殊性质 |
对于 $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$ 分。