题目描述

在一个城市中有 $N$ 个公交站点，编号为 $1$ 到 $N$，共有 $M$ 条双向的公交线路。每条公交线路连接两个站点，乘坐任意一条线路从一个站点到另一个站点需要 $1$ 个单位时间。

对于第 $i$ 条连接了 $U_i$ 和 $V_i$ 两个公交站点的线路，若 $U_i \neq 0$，则它连接站点 $U_i$ 和 $V_i$；若 $U_i = 0$，则表示该线路的一端固定为站点 $V_i$，另一端尚未确定。

你的任务是针对每个站点 $i$（$i = 1, 2, …, N$），假设所有未确定端点的公交线路的另一端都连接到站点 $i$，计算从站点 $1$ 到站点 $N$ 的最短时间。

如果无法通过公交线路从站点 $1$ 到达站点 $N$，则输出 $-1$。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示公交站点的数量和公交线路的数量。

接下来 $M$ 行，每行包含两个整数 $U_i$ 和 $V_i$，表示第 $i$ 条公交线路的两个端点。若 $U_i = 0$，表示该线路一端为站点 $V_i$，另一端未定。

输出格式

输出一行，包含 $N$ 个整数，用空格分隔。第 $i$ 个整数表示当所有未确定端点的公交线路都连接到站点 $i$ 时，从站点 $1$ 到站点 $N$ 的最短时间。若无法到达，输出 $-1$。

样例 #1

输入

3 2
0 2
1 2

输出

-1 -1 2

数据范围

对于 $100\%$ 的数据，满足 $2 \le N \le 3 \times 10^5$，$1 \le M \le 3 \times 10^5$，$0 \le U_i < V_i \le N$。