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，则输出 -1。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le \min(5 \cdot 10^5, \frac{n(n-1)}{2})$)，分别表示房间数量和连接的房间对数。

第二行包含 $n$ 个整数 $a_i$ ($1 \le a_i \le n$)，描述 Luka 的躲藏策略。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $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。

子任务

样例

输入 1

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

输出 1

-1 -1 -1 -1

输入 2

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

输出 2

1 2 2 2 1 1 1 1

说明 2

Marin 在第一步从房间 4 进入房间 8，在第二步回到房间 4。Luka 需要经过房间 4 才能从房间 7 到达房间 1，因此 Marin 可以在 2 步内找到 Luka。

输入 3

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

输出 3

0 1 1 2 1 1 2 1 1