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, сколько минимум строк нужно удалить, чтобы таблица стала прекрасной.
Выходные данные
В первой строке выведите одно целое число \(k\) — минимальное число строк, которые необходимо удалить.
Во второй строке выведите \(k\) различных чисел \(r_1, r_2, \ldots, r_k\), задающих строки, которые нужно удалить (\(1 \le r_i \le n\)), в любом порядке.
Если существует несколько решений, выведите любое из них.
Примечание
Таблица из первого примера приведена в условии задачи. Для нее уже верно, что:
- \(1\)-я и \(2\)-я строки имеют \(1\) в столбце \(7\).
- \(2\)-я и \(3\)-я строки имеют \(1\) в столбце \(15\).
Значит, исходная таблица уже прекрасная и мы не должны удалять ничего.
Во втором примере таблица следующая:
