P13344 [EGOI 2025] 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$，分别表示洞穴数量和水道数量。接下来 $M$ 行，每行两个整数 $a_i$ 和 $b_i$，表示当前有一条水道可从洞穴 $a_i$ 到洞穴 $b_i$。不会有自环，每对洞穴之间每个方向最多只会有一条水道。

输出一行 $N-1$ 个整数，第 $i$ 个整数（$0 \leq i \leq N-2$）表示从洞穴 $i$ 出发，在巨魔任意时机发动魔法的情况下，你**一定**能到达出口所需的最小移动次数。 注意不需要输出洞穴 $N-1$ 的答案（因为你一开始就在出口，可以立刻离开）。

### 样例说明 对于第一个样例，考虑你从洞穴 $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$ 你的解答将在一组测试组上进行评测，每组包含若干测试用例。要获得该测试组的分数，你需要通过该测试组的所有测试用例。 | 测试组 | 分值 | 限制条件 | | :-: | :-: | :-: | | 1 | 12 | $M = N - 1$，且 $a_i = i$，$b_i = i + 1$，即洞穴系统是一条链 $0 \rightarrow 1 \rightarrow 2 \rightarrow \ldots \rightarrow N-1$ | | 2 | 15 | 对每个 $0 \leq i \leq N-2$，都存在一条从 $i$ 直达 $N-1$ 的通道（可能还有其它通道） | | 3 | 20 | $N, M \leq 2000$ | | 4 | 29 | 每次离开某洞穴后，在反转发生前无法回到该洞穴（即所有通道构成有向无环图） | | 5 | 24 | 无额外限制 | 翻译由 ChatGPT-4.1 完成。