Problem
オセアニアの島々に点在する 1 つの州は、道路 (または橋) のネットワークを作成することを決定しました。各橋は双方向に移動できます。橋の建設のための順序計画が策定されており、すべての橋の建設後、各島から各島へ (おそらくいくつかの中間の島を通って) 車で橋を渡ることが可能になることが知られています
しかし、この瞬間は、すべての橋が建設される前に来るかもしれません.このような最小数の橋を決定する必要があります。橋の建設後 (計画で決定された順序で)、任意の島から別の島に移動できるようになります。
入力
最初の行には、島の数 N (1≤N≤10000) と平面図の橋の数 M (1≤M≤50000) の 2 つの数値が含まれています。次に、M 行があり、それぞれに 2 つの数値 x と y (1≤x,y≤N) が含まれます。これは、計画内の次の橋で接続されている都市の数です。
出力
プログラムは単一の数値を出力する必要があります。これは、建設された橋の最小数であり、その後、任意の島から他の島への移動が可能になります。
<本体>
| 入力 |
出力 |
|
4 5
1 2
1 3
2 3
3 4
4 1
|
4 |