{"raw_statement":[{"iden":"statement","content":"Marin 和 Luka 正在他们的房子里玩一个流行的儿童游戏——捉迷藏。这个房子共有 $n$ 个房间，有 $m$ 对房间通过一扇门连接。房间从 $1$ 到 $n$ 编号，并且任意两个房间之间是存在道路相连通的。\n\nLuka 想出了一个躲藏策略：当 Marin 进入房间 $v$ 时，Luka 会躲在房间 $a_v$ 里。在游戏的开始 Marin 选择他开始找人的房间 $v_0$，Luka 躲在房间 $a_{v_0}$里。在游戏的每一个回合，首先由 Marin 选择一个与当前相邻房间 $u$ 并进入。随后 Luka 知道 Marin 在房间 $u$ 中所以参照他的躲藏方式他会躲到房间 $a_u$ 中。注意到 Luka 可以选择任何抵达房间 $a_u$ 的路线并且在游戏的一个回合中他可以经过任意数量的房间。\n\n定义 Marin 找到了 Luka 为当他们两个都在同一个房间中的时候，这时游戏结束。\n\nMarin 发现了 Luka 的躲藏策略，所以她想要你考虑从每一个房间出发时，她是否可以在有限回合找到 Luka。如果可以，计算在理想状态下（Marin 尽可能减少回合数，Luka 尽可能增加回合数）最少需要的回合数。"},{"iden":"input","content":"第一行两个整数 $n,m$，分别表示房间的数量和相连房间的对数。\n\n第二行 $n$ 个整数 $a_i$，表示 Luka 的躲藏策略。\n\n在接下来的 $m$ 行中，每行两个整数 $x_i,y_i$，表示这两个房间是相连的。任意两个房间最多只有一条直接相连的道路。"},{"iden":"output","content":"一行 $n$ 个数，表示最少需要的回合数。如果无法在有限步中结束游戏，输出 $-1$。"},{"iden":"note","content":"**【样例解释 #2】**\n\nMarin 第一回合从房间 $4$ 进入房间 $8$，第二回合回到房间 $4$。Luka 需要经过房间 $4$ 才能从房间 $7$ 到房间 $1$。所以可以在两个回合找到。\n\n**【数据范围】**\n\n| 子任务 | 分值 | 特殊性质 |\n| :----------: | :----------: | :----------: |\n| $1$ | $15$ | $n\\le 1000,m\\le2000$ |\n| $2$ | $25$ | $m=n-1$ |\n|$3$ | $30$| Luka 的躲藏策略满足他永远不会躲在与 Marin 当前所在房间相邻或相同的房间，并且房子的结构满足游戏可以在最多有 $5$ 个不同房间独立于 Luka 的躲藏策略之外的情况下结束游戏。 \n| $4$ | $40$ | 无特殊性质 |\n\n对于 $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$。\n\n本题满分 $110$ 分。"}],"translated_statement":null,"sample_group":[["4 4\n3 4 1 2\n1 2\n2 3\n3 4\n4 1","-1 -1 -1 -1"],["8 9\n2 3 2 1 6 5 6 7\n1 2\n1 3\n2 4\n3 4\n4 5\n4 6\n6 7\n5 7\n4 8","1 2 2 2 1 1 1 1"],["9 8\n1 9 1 1 1 9 9 9 1\n1 2\n2 3\n3 4\n4 5\n5 6\n6 7\n7 8\n8 9","0 1 1 2 1 1 2 1 1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}