第25回日本情報オリンピック　二次予選

2025年12月15日
情報オリンピック日本委員会

問題文

JOI 国は N 個の街とそれらをつなぐ M 本の道からなる．街には 1 から N までの番号が，道には 1 から M までの番号が付けられている．道 i (1 ≦ i ≦ M) は街 A_i と街 B_i を双方向につないでいる．ここで，A_i < B_i である．また，どの 2 つの街のペアについても，それらをつなぐ道は高々 1 本である．すなわち，A_i ≠ A_j または B_i ≠ B_j (1 ≦ i < j ≦ M) である．

ビ太郎は現在街 s におり，旅行計画を立てている．旅行計画はビ太郎が訪れる街の番号の順番を表す数列 v = (v₁, v₂, …) で表される．ここで，v は 1 以上 N 以下の整数からなる，長さ 1 以上の数列である．ビ太郎は旅行で訪れる街の番号の順番に強いこだわりを持っているため，数列 v は，その長さを l としたとき，以下の条件をすべて満たす必要がある．

• v₁ = s．
• 各 j = 1, 2, …, l − 1 について，街 v_j と街 v_j+1 は道でつながれている．
• 各 j = 1, 2, …, 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, …, N それぞれについて，ビ太郎の質問に対する答えを計算したい．

JOI 国の街と道についての情報が与えられたとき，s = 1, 2, …, N それぞれについて，ビ太郎がどのような旅行計画を立てたとしても到達できない街の個数を求めるプログラムを作成せよ．

制約

• 1 ≦ N ≦ 300 000．
• 0 ≦ M ≦ 300 000．
• 1 ≦ A_i < B_i ≦ N (1 ≦ i ≦ M)．
• A_i ≠ A_j または B_i ≠ B_j (1 ≦ i < j ≦ M)．
• 入力される値はすべて整数である．

小課題

1. (12 点) N ≦ 1000，M = N − 1．さらに，(1, 2, …, N) を並べ替えて得られるある順列 P = (P₁, P₂, …, P_N) が存在し，各 i = 1, 2, …, N − 1 について，P_i と P_i+1 をつなぐ道が存在する．
2. (19 点) N ≦ 1000，M ≦ 1000．
3. (15 点) M = N − 1．さらに，(1, 2, …, N) を並べ替えて得られるある順列 P = (P₁, P₂, …, P_N) が存在し，各 i = 1, 2, …, N − 1 について，P_i と P_i+1 をつなぐ道が存在する．
4. (17 点) 各街について，その街と直接道でつながれている街は高々 2 つである．
5. (37 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N   M
A₁   B₁
A₂   B₂
:
A_M   B_M

出力

N 行出力せよ．k (1 ≦ k ≦ N) 行目には，s = k のときビ太郎がどのような旅行計画を立てたとしても到達できない街の個数を出力せよ．

入出力例

入力例 1
4 4
1 2
1 3
1 4
3 4

出力例 1
0
3
0
3

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
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 の制約を満たす．