AT_abc446_f [ABC446F] Reachable Set 2

$ N $ 頂点 $ M $ 辺の有向グラフ $ G $ が与えられます。 $ G $ の頂点は頂点 $ 1 $ 、頂点 $ 2 $ 、 $ \ldots $ 、頂点 $ N $ と番号付けられており、 $ i $ 番目 $ (1\leq i\leq M) $ の辺は頂点 $ U_i $ から頂点 $ V_i $ へ向かう辺です。 $ k=1,2,\ldots,N $ について以下の問題を解いてください。 > 高橋君の目標は、 $ G $ から（ $ 0 $ 個でも良い）いくつかの頂点、およびそれらの頂点を始点または終点として持つすべての辺を削除することで、次の条件をみたすようにすることです。 > > - 頂点 $ 1 $ から $ 0 $ 本以上のいくつかの辺を辿って到達可能な頂点が頂点 $ 1,2,\ldots,k $ のみである。 > > 高橋君が目標を達成することが可能か判定し、可能な場合は目標を達成するために高橋君が最低何個の頂点を削除する必要があるか求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_M $ $ V_M $

$ N $ 行出力せよ。 $ i $ 行目 $ (1\leq i\leq N) $ には、 $ k=i $ のときの問題の答えを出力せよ。 ここで、各問題に対する答えとして、高橋君が目標を達成することが不可能な場合は $ -1 $ を、そうでない場合は目標を達成するために削除する必要のある頂点の個数の最小値を出力せよ。

### Sample Explanation 1 - $ k=1 $ のとき、頂点 $ 2 $ を削除することによって目標を達成できます。このとき、頂点 $ 3,4,5 $ は削除せずとも頂点 $ 1 $ から到達できないことに注意してください。 $ 1 $ つも頂点を削除せずに目標を達成することはできないため、 $ 1 $ を $ 1 $ 行目に出力します。 - $ k=2 $ のとき、頂点 $ 4,5 $ を削除することにより目標を達成できます。 $ 1 $ つ以下の頂点を削除することによって目標を達成することは不可能なので、 $ 2 $ を $ 2 $ 行目に出力します。 - $ k=3 $ のとき、高橋君はどのように頂点を削除しても目標を達成できません。よって、 $ -1 $ を $ 3 $ 行目に出力します。 - $ k=4 $ のとき、頂点 $ 5 $ を削除することによって目標を達成できます。 $ 1 $ つも頂点を削除せずに目標を達成することはできないため、 $ 1 $ を $ 4 $ 行目に出力します。 - $ k=5 $ のとき、頂点を削除することなく目標を達成できます。よって、 $ 0 $ を $ 5 $ 行目に出力します。 ### Sample Explanation 2 $ G $ は連結とは限りません。また、 $ G $ は多重辺や自己ループを持つこともあります。 ### Constraints - $ 2\leq N\leq 3\times 10^5 $ - $ 1\leq M\leq 3\times 10^5 $ - $ 1\leq U_i,V_i\leq N $ - 入力はすべて整数