/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 300 points
Problem Statement
There are N cities numbered 1 through N, and M bidirectional roads numbered 1 through M. Road i connects City A_i and City B_i.
Snuke can perform the following operation zero or more times:
- Choose two distinct cities that are not directly connected by a road, and build a new road between the two cities.
After he finishes the operations, it must be possible to travel from any city to any other cities by following roads (possibly multiple times).
What is the minimum number of roads he must build to achieve the goal?
Constraints
- 2 \leq N \leq 100,000
- 1 \leq M \leq 100,000
- 1 \leq A_i < B_i \leq N
- No two roads connect the same pair of cities.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 : A_M B_M
Output
Print the answer.
Sample Input 1
3 1 1 2
Sample Output 1
1
Initially, there are three cities, and there is a road between City 1 and City 2.
Snuke can achieve the goal by building one new road, for example, between City 1 and City 3. After that,
- We can travel between 1 and 2 directly.
- We can travel between 1 and 3 directly.
- We can travel between 2 and 3 by following both roads (2 - 1 - 3).
配点 : 300 点
問題文
N 個の都市 (1 番から N 番まで) と M 個の双方向道路 (1 番から M 番まで) があります。 道路 i は都市 A_i と都市 B_i を結びます。
すぬけ君は、以下の操作を 0 回以上行うことができます。
- 道路で直接結ばれていない二つの異なる都市を選び、間に道路を作る。
操作を終えた後、どの都市からどの都市へも (場合によっては複数回) 道路をたどることで到達できるようになっていなければいけません。
目的を達成するために、最低何個の道路を作ればよいですか？
制約
- 2 \leq N \leq 100,000
- 1 \leq M \leq 100,000
- 1 \leq A_i < B_i \leq N
- どの二つの道路も同じ都市のペアを結ばない。
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 : A_M B_M
出力
答えを出力せよ。
入力例 1
3 1 1 2
出力例 1
1
最初に、都市が三つあり、都市 1 と都市 2 の間に道があります。
すぬけ君は、たとえば都市 1 と都市 3 の間に道を作ることによって目的を達成できます。 道を作った後、
- 都市 1 と 2 の間を直接旅行できます。
- 都市 1 と 3 の間を直接旅行できます。
- 都市 2 と 3 の間を両方の道を通ることで旅行できます。 (2 - 1 - 3)