4027. HS's bridge

【题目背景】

HS不想说话...。。。

【题目描述】

给定 $n$ 个点，每个点上有一个人，初始有 $i$ 到 $i+1，i \in [1,n)$ 共 $n-1$ 个桥梁。

给定 $m$ 对关系， $(a,b)$ 表示 $a$ 点上的人与 $b$ 点上的人有感情纠纷，所以 HS 不能让 $a,b$ 联通。

但是 HS 不喜欢拆桥梁，所以你要求满足 $m$ 个条件的最少拆除桥梁数。

【输入格式】

第一行两个整数 $n$,$m$，表示有 $n$ 个点，$m$ 条关系。

然后 $m$ 行有两个整数 $a,b$ 且 $a < b$，表示 $a$ 点上的人与 $b$ 点上的人有矛盾。

【输出格式】

一个整数表示最少拆除桥梁数。

【样例输入1】

5 2
1 4
2 5

【样例输出1】

1

【样例输入2】

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

【样例输出2】

4

【样例说明】

HS 不想告诉你。

大洋里

【数据规模与约定】

对于 $100\%$ 的数据，有 $a,b,n,m \le 2\times 10^5$。

HS 觉得这道题是签到，所以没有部分分。

【来源】

atcoder.jp/contests/abc103/tasks/abc103_d