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

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

JOI 国有 $N$ 个城市以及连接这些城市的 $M$ 条道路。城市编号为 $1$ 到 $N$ ，道路编号为 $1$ 到 $M$ 。道路 $i\,(1\leq i\leq M)$ 连接城市 $A_i$ 和城市 $B_i$ ，道路是双向的。这里， $A_i<B_i$ 。此外，对于任意一对不同的城市，连接它们的道路至多只有一条。也就是说， $A_i\neq A_j$ 或 $B_i\neq B_j$ （ $1\leq i<j\leq M$ ）。

比太郎现在位于城市 $s$ ，正在制定旅行计划。旅行计划以比太郎要依次访问的城市编号的序列 $v=(v_1,v_2,\ldots)$ 表示。这里， $v$ 是长度至少为 $1$ ，每项都是 $1$ 到 $N$ 的整数的序列。比太郎对旅行中访问城市的编号顺序有强烈的讲究，因此，当 $v$ 的长度为 $l$ 时，必须满足以下所有条件：

$v_1 = s$ 。
对于每个 $j=1,2,\ldots,l-1$ ，城市 $v_j$ 和城市 $v_{j+1}$ 之间有道路直接相连。
对于每个 $j=1,2,\ldots,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,\ldots,N$ 的每一种情况分别计算出比太郎提出的问题的答案。

现在给定 JOI 国的城市和道路信息，请你编写程序，对 $s=1,2,\ldots,N$ 的每一种情况，输出比太郎无论如何都无法到达的城市的数量。

输入格式

输入的格式如下：

$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
```
4 4
1 2
1 3
1 4
3 4
```
输出#1
```
0
3
0
3
```
输入#2
```
2 0
```
输出#2
```
1
1
```
输入#3
```
4 3
1 3
3 4
2 4
```
输出#3
```
2
1
1
3
```
输入#4
```
6 6
1 4
1 3
2 4
2 5
3 6
5 6
```
输出#4
```
1
1
3
5
3
5
```

说明/提示

小题目

（ $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}$ 的道路。
（ $19$ 分） $N\leq 1000$ ， $M\leq 1000$ 。
（ $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}$ 的道路。
（ $17$ 分）对于每个城市，与之直接相连的城市最多只有两个。
（ $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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页