Harmonious Graph

1000ms

262144K

Description:

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?

Input:

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

Output:

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

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Note:

In the first example, the given graph is not harmonious (for instance, $$$1 < 6 < 7$$$, node $$$1$$$ can reach node $$$7$$$ through the path $$$1 \rightarrow 2 \rightarrow 7$$$, but node $$$1$$$ can't reach node $$$6$$$). However adding the edge $$$(2, 4)$$$ is sufficient to make it harmonious.

In the second example, the given graph is already harmonious.

Informação

Provedor Codeforces

Código CF1253D