#237 Connecting a Graph

Loading problem...

Preparing the statement, recent submissions, and submit form.

#237 Connecting a Graph | DOJ

Authors: gs20036

Time limit: 1000 ms
Python time limit: 2000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

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_2\ v_2$ $\vdots$ $u_M\ v_M$

For each $i$ ( $1 \leq i \leq M$ ), this means that there is an undirected edge between $u_i$ and $v_i$ .

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)$ .
$1 \leq u_i,v_i \leq N$ ( $1 \leq i \leq M$ ).
$u_i \neq v_i$ ( $1 \leq i \leq M$ ).
Considering $(u_i,v_i)$ and $(v_i,u_i)$ as the same edge, no edge appears more than once in the input.

Subtasks

#	Score	Constraints
1	25	$N \leq 2\ 000$ . $M \leq 10\ 000$ .
2	20	$M=0$ .
3	55	No additional constraints.

Samples

Sample 1

Input

2
2
4

Output

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

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

Sample 3

Input

Output

All vertices are already connected, so no edge needs to be added.

Editorial

View editorial