N個の村がある。それぞれの村には1からNまでの番号がついている。昨今の合併ブームにより、いくつかの村が合併されることになった。合併された2つ以上の村は新しい1つの市となり、どの村とも合併されない村は村のままである。
あなたは、ある2つの村が合併後に同じ市になる、という情報を複数与えられる。その情報の組み合わせによって、3つ以上の村が1つの市になることもありうる。
合併後に同じ市になる村同士の情報が与えられたとき、合併後の市の数と村の数の差の絶対値を出力せよ。
入力は以下の形式で与えられる。
N M a1 b1 a2 b2 ... ai bi ... aM bM
1行目に村の数Nと合併についての情報の数Mが空白区切りで与えられる。
2行目からM+1行目に、合併についての情報を表す2つの整数aiとbiが空白区切りで与えらる。各情報はai番目の村とbi番目の村が合併後に同じ市になることを示す。ただし、ai=biを満たすような入力は与えられない。
村の数と市の数の差の絶対値を1行に出力せよ。
3 1 1 2
0
4 2 1 4 2 3
2
5 0
5
3 3 1 2 2 3 3 1
1
このケースではすべての村が1つの市に合併されることを表し、その市の中で合併される2つの村をつなぐつなぎ方の全通りが入力として与えられている。
3 2 1 2 2 3
1
このケースでは合併される3つの村をつなぐつなぎ方の全通りが入力として与えられているわけではないが、つながっている村をたどればすべての村にたどり着くことができるので、すべての村が一つの市に合併される。
5 4 1 2 2 3 3 4 4 5
1
10 5 3 4 1 2 9 6 2 6 2 9
2