B - 道路工事

B - 道路工事解説

実行時間制限: 2 sec / メモリ制限: 256 MB

大工のチョーさん(Daiku Cho)の町では道路の建設が進んでいます。チョーさんの町には N 個の交差点と M 個の道路があり、道路は異なる2つの交差点を双方向に結んでいます。不便なことに、ある交差点から別の交差点まで道路を使って行き来できるとは限りません。

チョーさんの建設会社は、異なる交差点を結ぶいくつかの道路を作って、N 個のどの交差点からも道路を使って他のどの交差点へも行けるようにしたいと思っています。

どの交差点からも道路を使って別のどの交差点にも行けるようにするには最小で何本の道路を建設する必要があるかを答えてください。ただし、すでにある道路でどの交差点からも別のどの交差点へ行けるとき、0 を出力してください。

入力は以下の形式で標準入力から与えられる。

N M
a_1 b_1
a_2 b_2
:
a_M b_M

1 行目には、チョーさんの町の交差点の数と、既にある道路の数を表す 2 つの整数 N (1 ≦ N ≦ 100,000) と M (0 ≦ M ≦ 100,000) がスペース区切りで与えられる。
2 行目から M 行には、既にある道路の情報が与えられる。そのうち i 行目には、i 番目の道路がつなぐ 2 つの交差点を表す 2 つの整数 a_i, b_i (1 ≦ a_i < b_i ≦ N がスペース区切りで与えられる。
同じ交差点をつなぐ道路が与えられることはない。すなわち、i,j (1≦i,j≦M) に対し、i≠j ならば a_i≠a_j または b_i≠b_j が成り立つ。

新たに建設する道路の最小の本数を1行目に出力せよ。

末尾の改行を忘れないこと。

4 2
1 2
1 3

交差点 1、2、3 は互いに道路でつながっているが、交差点 4 はつながっていない。例えば、交差点 1 と 4 を結ぶ道路を作れば十分である。