AT_abc401_e [ABC401E] Reachable Set

$ N $ 頂点 $ M $ 辺からなる無向グラフがあります。 頂点には $ 1,2,\ldots,N $ の番号がついており、 $ i $ 番目 $ (1\leq i\leq M) $ の辺は頂点 $ u _ i $ と頂点 $ v _ i $ を結んでいます。 $ k=1,2,\ldots,N $ について、次の問題を解いてください。 > 次の操作について考える。 > > - 頂点を一つ選ぶ。選んだ頂点と、選んだ頂点に接続する全ての辺をグラフから削除する。 > > 上の操作を繰り返すことで、次の条件を満たすことができるか判定せよ。 > > - 頂点 $ 1 $ から辺をたどって到達できる頂点の集合が、頂点 $ 1, $ 頂点 $ 2,\ldots, $ 頂点 $ k $ のちょうど $ 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=2 $ としたときの問題では、頂点 $ 3, $ 頂点 $ 4, $ 頂点 $ 5 $ の $ 3 $ つの頂点を選んで削除することで、頂点 $ 1 $ から到達できる頂点を頂点 $ 1, $ 頂点 $ 2 $ の $ 2 $ つだけにすることができます。 頂点を $ 2 $ つ以下だけ削除して条件を満たすことはできないため、 $ 2 $ 行目には `3` を出力してください。 また、 $ k=6 $ としたときの問題では、頂点をひとつも削除しないことで頂点 $ 1 $ から到達できる頂点を頂点 $ 1, $ 頂点 $ 2,\ldots, $ 頂点 $ 6 $ の $ 6 $ つにすることができます。 なので、 $ 6 $ 行目には `0` を出力してください。 ### Sample Explanation 3 辺が $ 1 $ つもない場合もあります。 ### Constraints - $ 1\leq N\leq2\times10 ^ 5 $ - $ 0\leq M\leq3\times10 ^ 5 $ - $ 1\leq u _ i\lt v _ i\leq N\ (1\leq i\leq M) $ - $ (u _ i,v _ i)\neq(u _ j,v _ j)\ (1\leq i\lt j\leq M) $ - 入力はすべて整数