| Codeforces Round 737 (Div. 2) |
|---|
| Закончено |
Moamen нарисовал таблицу из $$$n$$$ строк и $$$10^9$$$ столбцов, состоящую из цифр $$$0$$$ и $$$1$$$. Ezzat заметил, что Moamen рисует и заинтересовался, какое минимальное число строк нужно удалить, чтобы таблица стала прекрасной.
Таблица прекрасна, если и только если для каждых двух последовательных строк найдется хотя бы один столбец, содержащий $$$1$$$ в этих двух строках.
Ezzat опишет таблицу с помощью числа строк $$$n$$$, и $$$m$$$ отрезков таблицы, содержащих $$$1$$$. Каждый отрезок задается тремя числами $$$i$$$, $$$l$$$, и $$$r$$$, где $$$i$$$ задает номер строки, а $$$l$$$ и $$$r$$$ задают первый и последний столбцы отрезка в этой строке.
Например, если $$$n = 3$$$, $$$m = 6$$$, и заданы отрезки $$$(1,1,1)$$$, $$$(1,7,8)$$$, $$$(2,7,7)$$$, $$$(2,15,15)$$$, $$$(3,1,1)$$$, $$$(3,15,15)$$$, то таблица выглядит так:
Ваша задача — сказать Ezzat, сколько минимум строк нужно удалить, чтобы таблица стала прекрасной.
В первой строке содержатся два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 3\cdot10^5$$$).
В каждой из следующих $$$m$$$ строк содержатся три целых числа $$$i$$$, $$$l$$$ и $$$r$$$ ($$$1 \le i \le n$$$, $$$1 \le l \le r \le 10^9$$$). Каждая из этих $$$m$$$ строк означает, что строка $$$i$$$ содержит $$$1$$$ в столбцах с $$$l$$$ по $$$r$$$.
Обратите внимание, что отрезки могут накладываться.
В первой строке выведите одно целое число $$$k$$$ — минимальное число строк, которые необходимо удалить.
Во второй строке выведите $$$k$$$ различных чисел $$$r_1, r_2, \ldots, r_k$$$, задающих строки, которые нужно удалить ($$$1 \le r_i \le n$$$), в любом порядке.
Если существует несколько решений, выведите любое из них.
3 6 1 1 1 1 7 8 2 7 7 2 15 15 3 1 1 3 15 15
0
5 4 1 2 3 2 4 6 3 3 5 5 1 1
3 2 4 5
Таблица из первого примера приведена в условии задачи. Для нее уже верно, что:
- $$$1$$$-я и $$$2$$$-я строки имеют $$$1$$$ в столбце $$$7$$$.
- $$$2$$$-я и $$$3$$$-я строки имеют $$$1$$$ в столбце $$$15$$$.
Во втором примере таблица следующая:
