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

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\)) である．

ビ太郎は現在街 \(s\) におり，旅行計画を立てている．旅行計画はビ太郎が訪れる街の番号の順番を表す数列 \(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\) つ目の条件を満たさない．

ビ太郎は，どのような旅行計画を立てたとしても到達できない街，すなわち，上記の条件をすべて満たすどの数列 \(v\) にも登場しない番号の街が全部でいくつあるのか気になっている．

あなたは現在ビ太郎がどの街にいるかについて知らないので，\(s=1,2,\ldots,N\) それぞれについて，ビ太郎の質問に対する答えを計算したい．

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

• \(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\) のときビ太郎がどのような旅行計画を立てたとしても到達できない街の個数を出力せよ．

JOI 2026 · JCIOI · CC BY-SA 4.0