在一个城市中有 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, \ldots, 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 解释

• 当未定端点连接到站点 1 时，第 1 条线路连接站点 1 和 2，第 2 条线路也连接站点 1 和 2。无法从站点 1 到达站点 3，输出 -1。

• 当未定端点连接到站点 2 时，第 1 条线路连接站点 2 和 2（自环），第 2 条线路连接站点 1 和 2。仍无法到达站点 3，输出 -1。

• 当未定端点连接到站点 3 时，第 1 条线路连接站点 3 和 2，第 2 条线路连接站点 1 和 2。可以通过以下路径从站点 1 到站点 3：1->2->3，耗时 2 个单位的时间。

因此，输出为 -1\ -1\ 2。

数据范围

对于 100\% 的数据，满足 2 \leq N \leq 3 \times 10^5，1 \leq M \leq 3 \times 10^5，0 \leq U_i < V_i \leq N，对于任意 i \neq j 均满足 (U_i, V_i) \neq (U_j, V_j)。

月赛图论25年7月