← 返回题目列表

AtCoder · joi2026_yo2_e

E. 比特太郎的旅行 3

中文机器翻译题面 查看原题

配点: 100 点

問題文

JOI国家是 N 连接城市和城市 M 由书籍之路组成。在城市里 路上的号码最多为 1 减去 N 。 它们的编号最大为 1 减去 M 。路 i\,(1\leqq i \leqq M) 是城市 A_i 和城市 B_i 双向连接。在这里,A_i<B_i 。另外,哪个 2 即使是两个城市,也最多只有一条路连接它们。 1 这是一本书。也就是说,A_i\neq A_j 或 至少 B_i\neq B_j (1 \leqq i < j \leqq M)。

Bitaro 目前在镇上 我在 s 并正在制定旅行计划。旅行计划是一个数字序列,代表 Bitaro 将访问的城市的编号顺序。 它由 v=(v_1,v_2,\ldots) 表示。在这里,v 是 您也可以写 1 以上 N 长度,由小于或等于的整数组成 1 这是上面的序列。比特太郎对他旅行中所访问的城市的数字顺序非常讲究,所以他 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 不满足第一个条件。

Bitaro是一座无论你如何计划行程,即满足上述所有条件的任何数字序列都无法到达的城市。 我想知道总共有多少城镇的数字甚至没有出现在 v 中。

由于您不知道 Bitaro 目前在哪个城市,s=1,2,\ldots,N 对于每个,我想计算 Bitaro 问题的答案。

JOI 鉴于有关该国城市和道路的信息,s=1,2,\ldots,N 对于每个人,编写一个程序来查找 Bitaro 无法到达的城镇数量,无论他制定什么旅行计划。

制約

  • 1 \leqq N \leqq 300\,000.
  • 0 \leqq M \leqq 300\,000.
  • 1 \leqq A_i < B_i \leqq N (1 \leqq i \leqq M).
  • A_i\neq A_j 或 至少 B_i\neq B_j (1 \leqq i < j \leqq M).
  • 所有输入值都是整数。

小課題

  1. (12 点) N\leqq 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\leqq 1000,M\leqq 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 点)对于每个城镇,最多有与其有公路直接连接的城镇。 2 这是一个。
  5. (37 点)没有额外的限制。

入力

输入按以下格式给出。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M 

出力

N 输出行。k (1\leqq k \leqq N) 行中, 请输出第s=k 输出 Bitaro 无论他制定什么旅行计划都无法到达的城镇数量。 当


入力例 1

4 4
1 2
1 3
1 4
3 4

出力例 1

0
3
0
3

s=1 时,v 的可能序列是 v=(1),(1,2),(1,3),(1,4,1),(1,4,1,2) 等等。无论您如何计划行程,没有您到达不了的城市。 仅

s=2 时,v 的可能序列是 v=(2) 。无论你如何计划你的旅行, 无法访问 1,3,4 。

s=3 时,v 的可能序列是 v=(3),(3,4,1,2) 等等。无论您如何计划行程,没有您到达不了的城市。 仅

s=4 时,v 的可能序列是 v=(4) 。无论你如何计划你的旅行, 无法访问 1,2,3 。

此输入示例是一个小作业。 2, 5 满足约束。


入力例 2

2 0

出力例 2

1
1

s=1 时,v 的可能序列是 v=(1) 。无论你如何计划你的旅行, 无法访问 2 。

s=2 时,v 的可能序列是 v=(2) 。无论你如何计划你的旅行, 无法访问 1 。

此输入示例是一个小作业。 2, 4, 5 满足约束。


入力例 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

此输入示例是一个小作业。 2, 4, 5 满足约束。