No.317 辺の追加

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 48
作問者 : catuppercatupper
10 ProblemId : 896 / 出題時の順位表

問題文

頂点数 $N$, 辺数 $M$ のグラフ $G$ が与えられます。
$1 ≦ i ≦ N$ となる全ての整数 $i$ について以下の問いに答えてください。

. グラフ $G$ に( $0$ 個以上)好きなだけ辺を追加する時、頂点数 $i$ の連結成分を作れるか?作れるなら追加する辺の個数の最小値は何か?

入力

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\quad\vdots$
$u_M$ $v_M$

$1$ 行目にはグラフの頂点数を表す整数 $N(1 ≦ N ≦ 10^5)$ と辺数を表す整数 $M(1 ≦ M ≦ 2×10^5)$ が空白区切りで与えられる。続く $M$ 行のうち $i$ 行目 $(1 ≦ i ≦ M)$ には $i$ 番目の辺が結ぶ $2$ 頂点の番号 $u_i, v_i(1 ≦ u_i, v_i ≦ N)$ が空白区切りで与えられる。
グラフ $G$ には多重辺や自己辺があるかもしれない。

出力

出力は $N$ 行からなる。
$i$ 行目 $(1 ≦ i ≦ N)$ にはその $i$ に対する問いの答えを出力せよ。
答えが「つくれない」のときは整数の $-1$ を出力せよ。

サンプル

サンプル1
入力
6 3
2 3
4 5
5 6
出力
0
0
0
1
1
2

$3$ 頂点の連結成分、$2$ 頂点の連結成分、$1$ 頂点の連結成分が $1$ 個ずつあります。
辺を追加しなくても頂点数 $1,2,3$ の連結成分が作れます。
辺を $1$ 個追加することで頂点数 $4,5$ の連結成分が作れます。
辺を $2$ 個追加することで全ての連結成分をつなげて頂点数 $6$ の連結成分が作れます。

サンプル2
入力
9 9
2 3
4 5
5 6
6 4
7 8
8 9
9 1
1 1
3 2
出力
-1
0
0
0
1
1
1
-1
2

自己辺や多重辺がありうることに注意してください。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。