AT_abc257_f [ABC257F] Teleporter Setting

有 $N$ 个城镇和 $M$ 个传送器，城镇编号为 $1, 2, \ldots, N$。 每个传送器可以双向连接两个城镇，使用传送器可以在 $1$ 分钟内从一个城镇移动到另一个城镇。 第 $i$ 个传送器连接城镇 $U_i$ 和城镇 $V_i$，但有些传送器连接的其中一个城镇尚未确定。如果 $U_i=0$，则表示该传送器的一端连接城镇 $V_i$，另一端尚未确定。 对于 $i=1,2,\ldots,N$，请分别解决以下问题： > 将所有连接端未定的传送器的未定端都连接到城镇 $i$。此时，从城镇 $1$ 到城镇 $N$ 最少需要多少分钟？如果仅使用传送器无法从城镇 $1$ 到达城镇 $N$，请输出 $-1$。

输入按以下格式从标准输入给出。 > $N$ $M$ > $U_1$ $V_1$ > $U_2$ $V_2$ > $\vdots$ > $U_M$ $V_M$

请输出 $N$ 个整数，空格分隔。第 $k$ 个整数表示当所有未定端都连接到城镇 $k$ 时，从城镇 $1$ 到城镇 $N$ 的最短所需时间。

## 限制条件 - $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)$ - 输入均为整数 ## 样例解释 1 当所有未定端都连接到城镇 $1$ 时，第 $1$ 个和第 $2$ 个传送器都连接城镇 $1$ 和城镇 $2$。此时无法从城镇 $1$ 到达城镇 $3$。 当所有未定端都连接到城镇 $2$ 时，第 $1$ 个传送器连接城镇 $2$ 自身，第 $2$ 个传送器连接城镇 $1$ 和城镇 $2$。此时也无法从城镇 $1$ 到达城镇 $3$。 当所有未定端都连接到城镇 $3$ 时，第 $1$ 个传送器连接城镇 $3$ 和城镇 $2$，第 $2$ 个传送器连接城镇 $1$ 和城镇 $2$。此时可以按如下方式用 $2$ 分钟从城镇 $1$ 到达城镇 $3$： - 使用第 $2$ 个传送器从城镇 $1$ 到城镇 $2$。 - 使用第 $1$ 个传送器从城镇 $2$ 到城镇 $3$。 因此，依次输出 $-1,-1,2$。 请注意，可能存在连接同一城镇的传送器，或存在多个传送器连接同一对城镇。 由 ChatGPT 4.1 翻译