给你一个无向图,其中有 $$$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)$$$ 足以使其和谐。
在第二个示例中,给定的图已经是和谐的。