← 返回题目列表

AtCoder · abc103_d

D. 岛屿战争

中文机器翻译题面 查看原题

分数: 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

输出

打印必须拆除的最少桥梁数量。


示例输入 1

5 2
1 4
2 5

示例输出 1

1

这些要求可以通过拆除连接西边第二岛和第三岛的桥梁来满足。


示例输入 2

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

示例输出 2

2

示例输入 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