Description

你在一座废弃宅邸的中庭深处，发现了一本古老的书，揭示了波恩市最隐秘的秘密。在城市的地下深处，存在着一个由 $N$ 个洞穴组成的系统，这些洞穴通过 $M$ 条水道连接。每条水道中都流淌着单向的魔力水流，可以让船只沿着水道快速穿梭。洞穴系统目前只有一个出口，位于洞穴 $N-1$。

你对自己的发现感到无比兴奋，迫不及待地想要探索这些洞穴！然而，这个洞穴系统里住着一个巨魔，他喜欢戏弄不速之客。巨魔拥有有限的魔力——在你探险期间，他最多只能使用一次——可以用来修改洞穴系统，使你更难到达出口。

你的洞穴探险由若干轮组成。每一轮流程如下：

1. 首先，巨魔可以选择是否使用他的魔法。如果他使用，咒语会同时产生以下效果：

• 立刻反转所有水道的魔力水流方向：$a \rightarrow b$ 会变为 $b \rightarrow a$；
• 关闭位于洞穴 $N-1$ 的出口；
• 并在洞穴 $0$ 开启一个新的出口。

2. 然后，你可以选择一条从当前洞穴出发的水道，用船移动到另一个洞穴。为简便起见，每次乘船称为“一步移动”。

此外，每当你处于有出口的洞穴时，你会立刻离开洞穴系统。注意，如果你在某一轮时正好处于洞穴 $0$，而巨魔选择此时发动魔法，你也会立即通过新开的出口离开。

你的目标是尽快离开洞穴系统，好赶上 EGOI 的闭幕式。而巨魔的目标正好相反：他希望你在洞穴里待得越久越好。巨魔总是知道你的位置，并会选择对他最有利的时机发动魔法。

对于每个洞穴 $c$（$0 \leq c \leq N-2$），考虑你从洞穴 $c$ 出发的情形。对于这些情形中的每一个，请你计算无论巨魔何时发动魔法，你都一定能到达某个出口的最小移动次数。

假设如果不发动魔法，从洞穴 $0$ 总能到达任意洞穴，且从任意洞穴总能到达洞穴 $N-1$。

Input Format

第一行输入两个整数 $N$ 和 $M$，分别表示洞穴数量和水道数量。接下来 $M$ 行，每行两个整数 $a_i$ 和 $b_i$，表示当前有一条水道可从洞穴 $a_i$ 到洞穴 $b_i$。不会有自环，每对洞穴之间每个方向最多只会有一条水道。

Output Format

输出一行 $N-1$ 个整数，第 $i$ 个整数（$0 \leq i \leq N-2$）表示从洞穴 $i$ 出发，在巨魔任意时机发动魔法的情况下，你一定能到达出口所需的最小移动次数。

注意不需要输出洞穴 $N-1$ 的答案（因为你一开始就在出口，可以立刻离开）。

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

2 2 2 1

7 10
2 6
5 3
4 2
1 6
2 3
3 6
4 5
0 4
4 1
0 1

2 1 2 3 2 4

2 1
0 1

1

6 8
0 1
4 0
1 2
2 3
3 5
0 4
4 5
2 0

2 4 3 3 1

Hint

样例说明

对于第一个样例，考虑你从洞穴 $1$ 出发的情形。由于你无法预知方向反转会在何时发生，你应当一开始就朝着出口（洞穴 $4$）前进。你可以选择经由洞穴 $2$ 或洞穴 $3$。此处，经由洞穴 $3$ 是更优的选择，因为如果巨魔在你到达洞穴 $3$ 时发动魔法，你可以直接通过从洞穴 $3$ 到洞穴 $0$ 的通道离开洞穴系统。

更具体地说，巨魔有三种可能的施法时机：

• 如果巨魔在你还在洞穴 $1$ 时立刻发动魔法，你可以直接从洞穴 $1$ 前往洞穴 $0$ 并离开洞穴系统。
• 如果巨魔在你从洞穴 $1$ 到达洞穴 $3$ 后发动魔法，你可以直接从洞穴 $3$ 前往洞穴 $0$ 并离开。
• 如果巨魔在上述两种情况下都没有发动魔法，你将从洞穴 $3$ 前往洞穴 $4$ 并离开。

在第一种情况下你只需要移动一次；在其余两种情况下你需要移动两次。因此，这一情形的答案为 $\max(1, 2, 2) = 2$。

注意，如果你选择从洞穴 $1$ 前往洞穴 $2$，巨魔可以迫使你需要三步才能离开。

第一个和第二个样例满足测试组 3、4、5 的约束。第三个样例满足所有测试组的约束。第四个样例满足测试组 3 和 5 的约束，见下图。

约束与评分

• $2 \leq N \leq 200\,000$
• $1 \leq M \leq 500\,000$
• $0 \leq a_i, b_i \leq N - 1$ 且 $a_i \neq b_i$
• 在反转前，洞穴 $0$ 能到达所有洞穴，且所有洞穴都能到达洞穴 $N-1$

你的解答将在一组测试组上进行评测，每组包含若干测试用例。要获得该测试组的分数，你需要通过该测试组的所有测试用例。

翻译由 ChatGPT-4.1 完成。