CF1253D.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 \lt m \lt 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 \lt 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?

给你一个包含 $n$ 个节点和 $m$ 条边的无向图。节点编号为 $1$ 到 $n$。

当且仅当满足以下性质时，该图被称为和谐图：

• 对于任意三元组整数 $(l, m, r)$，若 $1 \le l \lt m \lt r \le n$，且存在一条从节点 $l$ 到节点 $r$ 的路径，则必定存在一条从节点 $l$ 到节点 $m$ 的路径。

换言之，在一个和谐图中，若从节点 $l$ 出发（$l \lt r$）能通过边到达节点 $r$，则也必须能到达所有中间节点 $l+1, l+2, \ldots, r-1$。

问：使该图变为和谐图所需添加的最少边数是多少？

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

第一行包含两个整数 $n$ 和 $m$（$3 \le n \le 200\ 000$，$1 \le m \le 200\ 000$）。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$），表示节点 $u$ 与节点 $v$ 之间存在一条边。

保证所给图是简单图（即不存在自环，且任意两个节点之间至多只有一条边）。

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

输出使图变为和谐图所需添加的最少边数。

In the first example, the given graph is not harmonious (for instance, $1 \lt 6 \lt 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.

在第一个例子中，给定的图不是和谐的（例如，$1 \lt 6 \lt 7$，节点 $1$ 可通过路径 $1 \rightarrow 2 \rightarrow 7$ 到达节点 $7$，但节点 $1$ 无法到达节点 $6$）。然而，添加边 $(2, 4)$ 就足以使其变为和谐图。

在第二个例子中，给定的图本身已是和谐的。