← 返回题目列表

AtCoder · awc0006_d

D. 保安人员的安置

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

分数: 400 分

问题陈述

高桥正在为一条长走廊制定安全计划,其中包括 N 部分(来自部分 1 至部分 N) 排列成一条直线。他必须确保所有部分都受到保安保护。

高桥已聚集 M 警卫候选人。各后卫候选人 i (1 \leq i \leq M) 可以覆盖节中的连续范围 L_i 至部分 R_i。也就是说,如果后卫候选人 i 已分配,部分 L_i, L_i + 1, \ldots, R_i 全部被覆盖。

高桥想要全部 N 要涵盖的部分。具体来说,他想选择一些 M 守卫候选者,使得所选守卫覆盖的部分的并集等于 \{1, 2, \ldots, N\}。每个后卫候选人可以选择或者不选择;同一候选人不能被多次选中。

找到需要分配的最少警卫人数。如果无论如何选择防护都无法覆盖所有部分,则输出 -1.

约束

  • 1 \leq N \leq 10^9
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
  • 所有输入均为整数

输入

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • 第一行包含一个整数 N 表示节数和整数 M 代表警卫候选人的数量,以空格分隔。
  • 从第 2 行到 (M + 1)第行,给出了每个守卫候选者可以覆盖的部分范围。
  • 的 树的 (i + 1)- 第行 (1 \leq i \leq M) 包含左端点 L_i 和右端点 守护候补区间的 R_i 保护候选人的部分范围 i 可以覆盖,用空格隔开。

输出

在一行中输出覆盖所有部分所需的最少警卫数量。如果不可能,则输出 -1.


示例输入 1

10 3
1 5
3 7
6 10

示例输出 1

2

示例输入 2

15 4
1 3
5 8
10 12
13 15

示例输出 2

-1

示例输入 3

1000000000 5
1 300000000
200000000 500000000
400000000 700000000
600000000 900000000
800000000 1000000000

示例输出 3

5