[ABC103D] Islands War

题面翻译

$N$ 个岛屿排成一列，相邻两个岛屿之间都有一座桥当做连接。

一天这些岛屿之间发生了 $M$ 场战争，第 $i$ 场是 $A_i$ 和 $B_i$ ，现在要求拆除一些桥梁使得任意两个发生了战争的岛屿都不可以到达彼此。

求最小要拆除的桥梁数。

题目描述

東西一列に並んだ $N$ 個の島と $N-1$ 本の橋があります。

$i$ 番目の橋は、西から $i$ 番目の島と西から $i+1$ 番目の島を接続しています。

ある日、いくつかの島同士で争いが起こり、島の住人たちから $M$ 個の要望がありました。

要望 $i$: 西から $a_i$ 番目の島と西から $b_i$ 番目の島の間で争いが起こったために、これらの島をいくつかの橋を渡って行き来できないようにしてほしい

あなたは橋をいくつか取り除くことでこれら $M$ 個の要望全てを叶えることにしました。

取り除く必要のある橋の本数の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $:$ $a_M$ $b_M$

输出格式

取り除く必要のある橋の本数の最小値を出力せよ。

样例 #1

样例输入 #1

5 2
1 4
2 5

样例输出 #1

1

样例 #2

样例输入 #2

9 5
1 8
2 7
3 5
4 6
7 9

样例输出 #2

2

样例 #3

样例输入 #3

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

样例输出 #3

4

提示

制約

• 入力は全て整数である
• $2\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ M\ \leq\ 10^5$
• $1\ \leq\ a_i$
• 組 $(a_i,\ b_i)$ は全て異なる

Sample Explanation 1

西から $2$ 番目の島と $3$ 番目の島を接続する橋を取り除くことで達成できます。