题目描述

A 国有 $n$ 个城市与 $m$ 条铁道，每条铁道连接两个（可以相同的）城市，火车通过每个铁道的时间均为 $1$ 个单位。铁道分为固定铁道与可变铁道两种，固定铁道的两端都是确定的，而可变铁道只有一端是固定的，另一端连接哪个城市是可变的，称为非固定端。

现在 A 国想对其铁道网络进行一次测试，你需要求出，对每个 $i$，若所有可变铁道的非固定端均与 $i$ 号城市连接，此时 $1$ 号城市到 $n$ 号城市所需的最短时间。若无法从 $1$ 号城市到达 $n$ 号城市，则请输出 $-1$。

输入格式

第一行包含两个正整数 $n,m$，表示城市数量与铁道数量。

接下来 $m$ 行，每行包含两个正整数 $u,v$，表示一条铁道的两个端点。特别地，非固定段以 $0$ 来表示。

输出格式

输出 $n$ 行，每行包含一个整数表示答案。

样例 #1

样例输入 #1

6 5
1 3
0 3
0 5
4 6
5 4

样例输出 #1

3
5
4
3
4
2

提示

样例输入/输出 2

详见下发文件下的 ex_railway2.in/out。

ex_railway1.in ex_railway1.out

ex_railway2.in ex_railway2.out

这个数据满足第 $4\sim 5$ 个测试点的限制。

数据规模与约定

对所有数据，保证 $1\le n,m\le 5\times 10^5$，保证一条铁道的 $u,v$ 不同时为 $0$。