Transitivity
Description
Given a simple undirected graph with $n$ vertices and $m$ edges, and it's guaranteed that $m<\frac{n(n-1)}{2}$ .
We define an undirected graph to be transitive if and only if for any two different vertices $u, v$ :
If there exists a path starting from $u$ and ending at $v$ in the graph, then there should exists an edge connected $u$ and $v$ in the graph.
Now you should add some undirected edges to the graph (add at least one edge). You need to ensure that after adding edges, the graph is still a simple undirected graph and is transitive.
The question is, how many edges need to be added at least?
Recall that a simple undirected graph is an undirected graph that does not have more than one edge between any two vertices and no edge starts and ends at the same vertex.
The first line contains two integers $n,m\ (3\le n\le 10^6, 1\le m\le \min(10^6, \frac{n(n-1)}{2}-1))$, indicating the number of vertices and edges in the given graph.
Then the following $m$ lines, each line contains two integers $u,v\ (1\le u,v\le n, u\not =v)$ , indicating an edge in the given graph. It's guaranteed that the graph is simple.
A single positive integer, representing the minimum number of edges you need to add.
Input
The first line contains two integers $n,m\ (3\le n\le 10^6, 1\le m\le \min(10^6, \frac{n(n-1)}{2}-1))$, indicating the number of vertices and edges in the given graph.
Then the following $m$ lines, each line contains two integers $u,v\ (1\le u,v\le n, u\not =v)$ , indicating an edge in the given graph. It's guaranteed that the graph is simple.
Output
A single positive integer, representing the minimum number of edges you need to add.
4 3
1 2
1 3
2 3
3