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

JOI 国は $ N $ 個の街とそれらをつなぐ $ M $ 本の道からなる．街には $ 1 $ から $ N $ までの番号が，道には $ 1 $ から $ M $ までの番号が付けられている．道 $ i\,(1\leqq i \leqq M) $ は街 $ A_i $ と街 $ B_i $ を双方向につないでいる．ここで， $ A_i 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\leqq k \leqq N) $ 行目には， $ s=k $ のときビ太郎がどのような旅行計画を立てたとしても到達できない街の個数を出力せよ．

### 小課題 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 $ 点) 追加の制約はない． ### Sample Explanation 1 $ 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 $ の制約を満たす． ### Sample Explanation 2 $ s=1 $ のとき， $ v $ としてありうる数列は $ v=(1) $ のみである．どのような旅行計画を立てたとしても，街 $ 2 $ に到達することはできない． $ s=2 $ のとき， $ v $ としてありうる数列は $ v=(2) $ のみである．どのような旅行計画を立てたとしても，街 $ 1 $ に到達することはできない． この入力例は小課題 $ 2, 4, 5 $ の制約を満たす． ### Sample Explanation 3 この入力例はすべての小課題の制約を満たす． ### Sample Explanation 4 この入力例は小課題 $ 2, 4, 5 $ の制約を満たす． ### Constraints - $ 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 $ )． - 入力される値はすべて整数である．