P14799 [JOI 2026 二次预选] 比太郎之旅 3 / Bitaro's Travel 3

JOI 国由 $N$ 个城市和连接它们的 $M$ 条道路构成。城市被编号为 $1$ 到 $N$，道路被编号为 $1$ 到 $M$。道路 $i \ (1 \le i \le M)$ 双向连接城市 $A_i$ 和城市 $B_i$。这里，$A_i < B_i$。此外，对于任意两个城市的配对，连接它们的道路最多只有 $1$ 条。也就是说，$A_i \ne A_j$ 或 $B_i \ne B_j \ (1 \le i < j \le M)$。 比太郎现在在城市 $s$，正在制定旅行计划。旅行计划用数列 $v = (v_1, v_2, \dots)$ 表示，它表示比太郎将访问的城市编号的顺序。这里，$v$ 是由 $1$ 以上 $N$ 以下的整数组成的、长度至少为 $1$ 的数列。由于比太郎对旅行中访问城市编号的顺序有很强的执念，数列 $v$ 在其长度为 $l$ 时，必须满足以下所有条件。 1. $v_1 = s$。 2. 对于各个 $j = 1, 2, \dots, l - 1$，城市 $v_j$ 与城市 $v_{j+1}$ 由道路连接。 3. 对于各个 $j = 1, 2, \dots, l - 1$，当 $j$ 为奇数时有 $v_j < v_{j+1}$ 成立，当 $j$ 为偶数时有 $v_j > v_{j+1}$ 成立。 例如，$v = (2)$ 和 $v = (1, 4, 1, 5, 3)$ 满足第 $3$ 个条件，但 $v = (3, 2)$ 不满足第 $3$ 个条件。 比太郎想知道：无论制定怎样的旅行计划都无法到达的城市，即在满足上述所有条件的任意数列 $v$ 中都不会出现其编号的城市，总共有多少个。 由于你不知道比太郎当前在什么城市，因此希望对 $s = 1, 2, \dots, N$ 各自，计算比太郎问题的答案。 给定关于 JOI 国的城市与道路的信息，请编写程序，对 $s = 1, 2, \dots, N$ 各自，求出无论比太郎制定怎样的旅行计划都无法到达的城市个数。

输入按以下格式给出。 > $N \ \ M$ > $A_1 \ \ B_1$ > $A_2 \ \ B_2$ > $\vdots$ > $A_M \ \ B_M$

输出 $N$ 行。第 $k \ (1 \le k \le N)$ 行输出当 $s = k$ 时，无论比太郎制定怎样的旅行计划都无法到达的城市个数。

### 样例解释 #### 样例 $1$ 解释 当 $s = 1$ 时，作为 $v$ 可能的数列有 $v = (1)$、$v = (1, 2)$、$v = (1, 3)$、$v = (1, 4, 1)$、$v = (1, 4, 1, 2)$ 等。不存在无论制定怎样的旅行计划都无法到达的城市。 当 $s = 2$ 时，作为 $v$ 可能的数列只有 $v = (2)$。无论制定怎样的旅行计划，都无法到达城市 $1, 3, 4$。 当 $s = 3$ 时，作为 $v$ 可能的数列有 $v = (3)$、$v = (3, 4, 1, 2)$ 等。不存在无论制定怎样的旅行计划都无法到达的城市。 当 $s = 4$ 时，作为 $v$ 可能的数列只有 $v = (4)$。无论制定怎样的旅行计划，都无法到达城市 $1, 2, 3$。 该输入示例满足子任务 $2, 5$ 的约束。 #### 样例 $2$ 解释 当 $s = 1$ 时，作为 $v$ 可能的数列只有 $v = (1)$。无论制定怎样的旅行计划，都无法到达城市 $2$。 当 $s = 2$ 时，作为 $v$ 可能的数列只有 $v = (2)$。无论制定怎样的旅行计划，都无法到达城市 $1$。 该输入示例满足子任务 $2, 4, 5$ 的约束。 #### 样例 $3$ 解释 该输入示例满足所有子任务的约束。 #### 样例 $4$ 解释 该输入示例满足子任务 $2, 4, 5$ 的约束。 ### 约束 - $1 \le N \le 300\,000$。 - $0 \le M \le 300\,000$。 - $1 \le A_i < B_i \le N \ (1 \le i \le M)$。 - $A_i \ne A_j$ 或 $B_i \ne B_j \ (1 \le i < j \le M)$。 - 输入的值全部为整数。 ### 子任务 - （12 分）$N \le 1000$，$M = N - 1$。另外，存在一个将 $(1, 2, \dots, N)$ 重新排列得到的某个排列 $P = (P_1, P_2, \dots, P_N)$，并且对各个 $i = 1, 2, \dots, N - 1$，存在一条连接 $P_i$ 与 $P_{i+1}$ 的道路。 - （19 分）$N \le 1000$，$M \le 1000$。 - （15 分）$M = N - 1$。另外，存在一个将 $(1, 2, \dots, N)$ 重新排列得到的某个排列 $P = (P_1, P_2, \dots, P_N)$，并且对各个 $i = 1, 2, \dots, N - 1$，存在一条连接 $P_i$ 与 $P_{i+1}$ 的道路。 - （17 分）对每个城市，与该城市直接由道路连接的城市最多为 $2$ 个。 - （37 分）没有额外约束。