← 返回题目列表

Codeforces · 1253/D

D. 和谐图

中文机器翻译题面 查看原题

给你一个无向图,其中有 $$$n$$$ 个节点和 $$$m$$$ 个边。节点编号从 $$$1$$$ 到 $$$n$$$。

当且仅当以下属性成立时,该图才被认为是和谐的:

- 对于每个整数三元组$$$(l, m, r)$$$,使得$$$1 \le l < m < r \le n$$$,如果存在从节点$$$l$$$到节点$$$r$$$的路径,则存在从节点$$$l$$$到节点$$$m$$$的路径。

换句话说,在和谐图中,如果从节点 $$$l$$$ 我们可以通过边 ($$$l < r$$$) 到达节点 $$$r$$$,那么我们也应该能够到达节点 $$$(l+1), (l+2), \ldots, (r-1)$$$ 。

为了使图形和谐,我们需要添加的最少边数是多少?

输入

第一行包含两个整数 $$$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$$$ 和 $$$u$$$ 之间有一条边$$$v$$$。

保证给定的图是简单的(不存在自环,并且每对节点之间至多有一条边)。

输出

打印我们必须添加到图形中以使其和谐的最少边数。

示例

输入 #1

14 8
1 2
2 7
3 4
6 3
5 7
3 8
6 8
11 12

输出 #1

1

输入 #2

200000 3
7 9
9 8
4 5

输出 #2

0

注意

在第一个示例中,给定的图不和谐(例如,$$$1 < 6 < 7$$$,节点$$$1$$$可以通过路径$$$1 \rightarrow 2 \rightarrow 7$$$到达节点$$$7$$$,但节点$$$1$$$无法到达节点$$$6$$$)。然而,添加边缘 $$$(2, 4)$$$ 足以使其和谐。

在第二个示例中,给定的图已经是和谐的。