100 #ABC103D. [ABC103D] Islands War

[ABC103D] Islands War

题目描述

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

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

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

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

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

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

输入格式

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

N N M M a1 a_1 b1 b_1 a2 a_2 b2 b_2 : : aM a_M bM b_M

输出格式

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

题目大意

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

一天这些岛屿之间发生了 MM 场战争,第 ii 场是 AiA_iBiB_i ,现在要求拆除一些桥梁使得任意两个发生了战争的岛屿都不可以到达彼此。

求最小要拆除的桥梁数。

5 2
1 4
2 5
1
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

提示

制約

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

Sample Explanation 1

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