配点 : $400$ 点

問題文

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

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

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

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

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

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

制約

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

入力

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

$N$ $M$

$a_1$ $b_1$

$a_2$ $b_2$

$:$

$a_M$ $b_M$

出力

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

5 2
1 4
2 5

1

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

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

2

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

4