题目描述

存在 $n$ 个小镇，$m$ 条传送通道，第 $i$ 条双向连结 $u_i,v_i$ 两个小镇，经过每个传送通道需要花费 $1$ 分钟。特别地，可能存在 $u_i=0$，表示该条传送通道只规定了一端，另一端待定。存在 $n$ 个独立询问，对于 $i=1,2,⋯,n$ ，钦定所有未确定的 $u_i$ 均为 $i$ ，求从小镇 $1$ 到小镇 $n$ 最小耗费的时间。若无法到达输出 $−1$ 。

输入格式

第一行输入两个整数 $n,m$ 。

接下来 $m$ 行，每行输入两个整数 $u_i,v_i$ 。

输出格式

输出一行 $n$ 个整数，表示每个询问的答案。

输入输出样例 #1

输入 #1

3 2
0 2
1 2

输出 #1

-1 -1 2

输入输出样例 #2

输入 #2

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

输出 #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$
• 没有重边

大样例下载