← 返回题目列表

Codeforces · 1932/F

F. 喂猫

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

有一个有趣的游戏,你需要喂来来去去的猫。游戏的级别由 $$$n$$$ 个步骤组成。有$$$m$$$猫;猫 $$$i$$$ 的出现顺序为从 $$$l_i$$$ 到 $$$r_i$$$(含)。在每个步骤中,您可以喂食当前存在的所有猫,也可以不执行任何操作。

如果你多次喂同一只猫,它就会吃得过多,你就会立即输掉游戏。您的目标是喂养尽可能多的猫而不导致任何猫吃得过多。

找出您可以喂养的猫的最大数量。

形式上,您需要从 $$$1$$$ 到 $$$n$$$ 的线段中选择几个整数点,使得在给定的线段中,没有一个线段覆盖两个或多个选定的点,并且尽可能多的线段覆盖选定的点之一。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le m\le 2\cdot 10^5$$$)。

接下来的 $$$m$$$ 行的第 $$$i$$$ 行包含一对整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$)。

所有测试的 $$$n$$$ 总和不超过 $$$10^6$$$,所有测试的 $$$m$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数,即您可以喂养的猫的最大数量。

示例

输入 #1

3
15 6
2 10
3 5
2 4
7 7
8 12
11 11
1000 1
1 1000
5 10
1 2
3 4
3 4
3 4
3 4
1 1
1 2
3 3
3 4
3 4

输出 #1

5
1
10

注意

在第一个示例中,喂养五只猫的方法之一是按步骤 $$$4$$$ 和 $$$11$$$ 喂养。

- 在步骤 $$$4$$$ 中,猫 $$$1$$$、$$$2$$$ 和 $$$3$$$ 将被喂食。
- 在步骤$$$11$$$,猫$$$5$$$和$$$6$$$将被喂食。