题目背景

在遥远的「蔡村王国」，小蔡同学被任命为 传送门网络部部长。

全村共有 $N$ 个村庄，由 $M$ 个传送门构成基础传送网络。

每个传送门可以连接两个村庄，并支持 双向传送，每次传送耗时 1 分钟。 然而，由于部分施工图纸遗失，有些传送门只记录了一端村庄的信息，另一端暂未确定。

题目描述

你将获得如下信息：

$N$：村庄数量（编号为 $1$ 到 $N$）

$M$：传送门数量

每个传送门连接两个村庄 $(U_i, V_i)$

若 $U_i = 0$，表示这个传送门的一端是 $V_i$，另一端尚未确定

你的任务是：

对每一个 $i = 1, 2, \dots, N$，将所有未定传送门的另一端连接到村庄 $i$， 然后计算从村庄 $1$ 到村庄 $N$ 的最短传送时间（以分钟计）。若无法到达，则输出 $-1$。

输入格式

输入共 $M + 1$ 行：

第一行输入两个整数 $N, M$：

接下来 $M$ 行，每行两个整数 $U_i, V_i$：

若 $U_i = 0$，表示未定端点的传送门，仅已知另一端为 $V_i$

否则，该传送门连接村庄 $U_i$ 与 $V_i$

注意：所有 $(U_i, V_i)$ 均不相同。

输出格式

输出一行 $N$ 个整数，第 $i$ 个整数表示：

将所有未定传送门连接到村庄 $i$ 后，

从村庄 $1$ 到村庄 $N$ 的最短传送时间

若无法传送到达，则该位置输出 $-1$

样例

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

提示

有可能出现 自环（传送门连接同一个村庄）

有可能出现 重边（多条传送门连接同一对村庄）

所有传送门都是 双向可通行

样例1解释

若将未定传送门连接到村庄 $1$ 或 $2$，无法连通村庄 $3$

若连接到村庄 $3$，可形成路径：$1 \rightarrow 2 \rightarrow 3$，共耗时 $2$ 分钟

数据范围

存在$20\%$的数据,$1 \leq N \leq 10^3$,$1 \leq M \leq 10^3$

$100\%的数据$,$2 \leq N \leq 3 \times 10^5$,$1 \leq M \leq 3 \times 10^5$