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