#237 Connecting a Graph

Statement

Statement language

You are given an undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1,2,\cdots,N$ .

Two vertices $u,v$ are connected if it is possible to start from $u$ and reach $v$ by moving along edges zero or more times. In particular, every vertex is connected to itself.

You want to add some new undirected edges so that every pair of vertices is connected. Find the minimum number of edges that must be added.

Input

The input is given in the following format.

$N\ M$ $u_1\ v_1$ $u_{}$

Output

Print the minimum number of edges that must be added.

Constraints

$1 \leq N \leq 200\ 000$ .
$0 \leq M \leq \min\left(\frac{N(N-1)}{2}, 300\ 000\right)$ .

Subtasks

#	Score	Constraints
1	25	$N \leq 2\ 000$ . $M \leq 10\ 000$ .
2	20	$M=0$ .

Samples

Sample 1

Input

2
2
4

Output

1

The initial graph has two connected components: $\{1,2\}$ and $\{3,4\}$ . Adding one edge between the two components makes all vertices connected.

Sample 2

Input

5 0

Output

4

There are no edges, so each of the $5$ vertices is its own connected component. Therefore, edges are necessary.