You are given an undirected graph with n vertices labelled 0..n-1 and m edges. You may add new edges between any pair of vertices.
Report the minimum number of edges you must add so that the entire graph becomes connected (every vertex reachable from every other). If the graph is already connected the answer is 0.
Input format
Line 1: two integers n and m.
The next m lines each contain two integers u v, an undirected edge.
Output format
A single integer: the minimum number of extra edges required.
Constraints
- 1 <= n <= 100000
- 0 <= m <= 200000
- 0 <= u, v <= n - 1
- The graph may contain self-loops and repeated edges.