CF1253D Harmonious Graph

给定一个无向图，包含 $n$ 个节点和 $m$ 条边。节点编号从 $1$ 到 $n$。 当且仅当满足以下性质时，称该图是“和谐”的： - 对于所有满足 $1 \le l < m < r \le n$ 的整数三元组 $(l, m, r)$，如果存在一条从节点 $l$ 到节点 $r$ 的路径，则必须存在一条从节点 $l$ 到节点 $m$ 的路径。 换句话说，在和谐图中，如果从节点 $l$ 可以通过若干条边到达节点 $r$（且 $l < r$），那么从 $l$ 到 $(l+1), (l+2), \ldots, (r-1)$ 的所有节点也都必须可达。 请问，最少需要添加多少条边，才能使该图变为和谐图？

第一行包含两个整数 $n$ 和 $m$（$3 \le n \le 200\,000$，$1 \le m \le 200\,000$）。 接下来 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$），表示在节点 $u_i$ 和节点 $v_i$ 之间有一条无向边。 保证给定的图是简单图（没有自环，每对节点之间至多有一条边）。

输出一个整数，表示最少需要添加多少条边才能使图变为和谐图。

在第一个样例中，原图不是和谐图（例如 $1 < 6 < 7$，节点 $1$ 可以通过路径 $1 \rightarrow 2 \rightarrow 7$ 到达节点 $7$，但节点 $1$ 无法到达节点 $6$）。然而，只需添加一条边 $(2, 4)$ 即可使其变为和谐图。 在第二个样例中，原图已经是和谐图。 由 ChatGPT 4.1 翻译