题目描述

存在 $n$ 个小镇，$m$ 条传送通道，第 $i$ 条双向连结 $u_i, v_i$ 两个小镇，经过每个传送通道需要花费 $1$ 分钟。

特别地，可能存在 $u_i = 0$，表示该条传送通道只规定了一端，另一端待定。

存在 $n$ 个独立询问，对于 $i = 1, 2, \cdots, n$，钦定所有未确定的 $u_i$ 均为 $i$，求从小镇 $1$ 到小镇 $n$ 最小耗费的时间。若无法到达输出 $-1$。

输入格式

第一行输入 $N$ $M$

接下来 $M$ 行每行两个整数输入 $U_i$ $V_i$

输出格式

输出 $N$ 个空格隔开的整数

3 2
0 2
1 2

-1 -1 2

5 5
1 2
1 3
3 4
4 5
0 2

3 3 3 3 2

提示

• $2\ \leq\ N\ \leq\ 3\times\ 10^5$
• $1\leq\ M\leq\ 3\times\ 10^5$
• $0\leq\ U_i\ <\ V_i\leq\ N$
• $i\ \neq\ j$ 时满足 $(U_i,V_i)\neq\ (U_j,V_j)$