Contest Duration: - (local time) (100 minutes) Back to Home
C - Connect Cities /

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


### 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).

### 問題文

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 と都市 3 の間に道を作ることによって目的を達成できます。 道を作った後、

• 都市 12 の間を直接旅行できます。
• 都市 13 の間を直接旅行できます。
• 都市 23 の間を両方の道を通ることで旅行できます。 (2 - 1 - 3)