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

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$。

**【样例解释 #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$ 分。