A13003 | Harmonious Graph

You're given an undirected graph with $n$ nodes and $m$ edges. Nodes are numbered from $1$ to $n$ .

The graph is considered harmonious if and only if the following property holds:

- For every triple of integers $(l, m, r)$ such that $1 \le l < m < r \le n$ , if there exists a path going from node $l$ to node $r$ , then there exists a path going from node $l$ to node $m$ .

In other words, in a harmonious graph, if from a node $l$ we can reach a node $r$ through edges ( $l < r$ ), then we should able to reach nodes $(l+1), (l+2), \ldots, (r-1)$ too.

What is the minimum number of edges we need to add to make the graph harmonious?

The first line contains two integers $n$ and $m$ ( $3 \le n \le 200\ 000$ and $1 \le m \le 200\ 000$ ).

The $i$ -th of the next $m$ lines contains two integers $u_i$ and $v_i$ ( $1 \le u_i, v_i \le n$ , $u_i \neq v_i$ ), that mean that there's an edge between nodes $u$ and $v$ .

It is guaranteed that the given graph is simple (there is no self-loop, and there is at most one edge between every pair of nodes).

Print the minimum number of edges we have to add to the graph to make it harmonious.