Codeforces Round 927 (Div. 3) |
---|
Закончено |
Существует увлекательная игра, в которой вам нужно кормить кошек, которые приходят и уходят. Уровень игры состоит из $$$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$$$).
$$$i$$$-я из следующих $$$m$$$ строк содержит пару целых чисел $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).
Сумма $$$n$$$ для всех тестов не превышает $$$10^6$$$, сумма $$$m$$$ для всех тестов не превышает $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — максимальное количество кошек, которых вы можете покормить.
315 62 103 52 47 78 1211 111000 11 10005 101 23 43 43 43 41 11 23 33 43 4
5 1 10
В первом примере один из способов покормить пять кошек — это покормить их на шагах $$$4$$$ и $$$11$$$.
Название |
---|