题目描述

有 $N$ 个站点和 $M$ 条双向线路。每条线路的长度均为 $1$。若一条线路记为 $(U_i,V_i)$ 且 $U_i\ne0$，它连接站点 $U_i$ 和 $V_i$；若 $U_i=0$，它的一端是 $V_i$，另一端尚未确定。

对于每个站点 $i$，假设所有未确定的端点都连接到站点 $i$，请计算站点 $1$ 到站点 $N$ 的最短路长度。若无法到达，输出 $-1$。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，每行包含两个整数 $U_i,V_i$。

输出格式

输出一行 $N$ 个整数，第 $i$ 个整数表示所有未确定端点连接到站点 $i$ 时的答案。数字之间用一个空格分隔。

样例

3 2
0 2
1 2

-1 -1 2

数据范围与提示

• $2\le N\le3\times10^5$
• $1\le M\le3\times10^5$
• $0\le U_i<V_i\le N$