AT_joi2026_yo2_e ビ太郎の旅 3 (Bitaro's Travel 3)

JOI 国有 $N$ 个城市以及连接这些城市的 $M$ 条道路。城市编号为 $1$ 到 $N$，道路编号为 $1$ 到 $M$。道路 $i\,(1\leq i\leq M)$ 连接城市 $A_i$ 和城市 $B_i$，道路是双向的。这里，$A_i

输入的格式如下： > $N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$

输出 $N$ 行。对于第 $k$ 行（$1\leq k\leq N$），输出当 $s=k$ 时，比太郎无论如何都无法到达的城市的数量。

## 小题目 1. （$12$ 分）$N\leq 1000$，$M=N-1$。并且，存在将 $(1,2,\ldots,N)$ 排列得到的某个排列 $P=(P_1, P_2, \ldots, P_N)$，对于每个 $i=1,2,\ldots,N-1$，存在一条连接 $P_i$ 和 $P_{i+1}$ 的道路。 2. （$19$ 分）$N\leq 1000$，$M\leq 1000$。 3. （$15$ 分）$M=N-1$。并且，存在将 $(1,2,\ldots,N)$ 排列得到的某个排列 $P=(P_1, P_2, \ldots, P_N)$，对于每个 $i=1,2,\ldots,N-1$，存在一条连接 $P_i$ 和 $P_{i+1}$ 的道路。 4. （$17$ 分）对于每个城市，与之直接相连的城市最多只有两个。 5. （$37$ 分）没有额外的限制。 ## 样例解释 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 \leq N \leq 300,000$。 - $0 \leq M \leq 300,000$。 - $1 \leq A_i < B_i \leq N$（$1 \leq i \leq M$）。 - $A_i\neq A_j$ 或 $B_i\neq B_j$（$1 \leq i < j \leq M$）。 - 输入的值均为整数。 由 ChatGPT 5 翻译