Connecting a Graph

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.

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$.

Print the minimum number of edges that must be added.

• $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.