题目描述

题目译自 European Girls' Olympiad in Informatics 2025 Day2 T2. Currents

在波恩市一座废弃房屋的中庭深处，你发现了一本古老的书，揭示了这个城市最隐秘的秘密。在城市深处，有一个由 $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$。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$，其中 $N$ 是洞穴数量，$M$ 是水道数量。

接下来的 $M$ 行每行包含两个整数 $a_{i}$ 和 $b_{i}$，表示当前可以用来从洞穴 $a_{i}$ 前往洞穴 $b_{i}$ 的水道。没有水道将洞穴连接到自身。对于每对洞穴，每个方向最多只有一条水道。

输出格式

输出一行包含 $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

对于第一个样例，考虑你从洞穴 $1$ 开始的情况。由于你不知道方向反转何时会发生，你应该开始朝洞穴 $4$ 的出口移动。你可以通过洞穴 $2$ 或洞穴 $3$ 到达。选择通过洞穴 $3$ 是更好的选择，因为如果方向反转在你到达那里时发生，你将有一条水道可以直接从洞穴 $3$ 到洞穴 $0$，然后你就可以离开洞穴系统。

更具体地说，巨魔决定使用魔法力量的时机只有三种可能性：

• 如果巨魔在你位于洞穴 $1$ 时立即使用他的力量，你可以直接从洞穴 $1$ 到洞穴 $0$ 并离开。
• 如果巨魔在你从洞穴 $1$ 到洞穴 $3$ 后使用他的力量，你可以直接从洞穴 $3$ 到洞穴 $0$ 并离开。
• 如果巨魔在这两种情况下都不使用他的力量，你将从洞穴 $3$ 到洞穴 $4$ 并离开。

在第一种选择中你只需要移动一次，在其他两种选择中你移动了两次。这意味着此情况的答案是 $\max(1, 2, 2)=2$。

注意，如果你选择从洞穴 $1$ 到洞穴 $2$，巨魔可以迫使你移动三次。

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

第二个样例满足子任务 $3, 4, 5$ 的限制条件。

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

第四个样例满足子任务 $3, 5$ 的限制条件。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 200000$。
• $1 \leq M \leq 500000$。
• $0 \leq a_{i}, b_{i} \leq N-1$ 且 $a_{i} \neq b_{i}$。
• 在方向反转之前，洞穴 $0$ 可以到达所有洞穴，并且从所有洞穴都可以到达洞穴 $N-1$。

详细子任务附加限制及分值如下表所示。