配点: 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).
- 所有输入值都是整数。
小課題
- (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} 。
- (19 点) N\leqq 1000,M\leqq 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 点)对于每个城镇,最多有与其有公路直接连接的城镇。 2 这是一个。
- (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 满足约束。