D2. Давай дружить, не бойся (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Обратите внимание на необычное распределение баллов между D1 и D2. Эта задача значительно сложнее D1.

Это сложная версия задачи. Отличие между версиями состоит в том, что в этой версии $$$0 \le m \le 2 \cdot 10^5$$$. Делать взломы можно, только если решены все версии этой задачи.

Вы прячетесь от грозного лорда Верити.

В ряд расположены $$$n$$$ возможных мест для укрытия, пронумерованных от $$$1$$$ до $$$n$$$ слева направо. Вы можете спрятаться ровно в одном месте.

Чтобы найти вас, лорд Верити может установить специальные детекторы. Каждый детектор покрывает отрезок из последовательных мест и сообщает, находитесь ли вы в одном из мест этого отрезка. Все детекторы срабатывают одновременно, поэтому отрезки для всех детекторов нужно выбрать до получения каких-либо показаний.

У лорда Верити уже есть $$$m$$$ детекторов; $$$i$$$-й из них покрывает места от $$$l_i$$$ до $$$r_i$$$. Найдите минимальное число дополнительных детекторов, которые лорду Верити нужно установить, чтобы, где бы вы ни спрятались, показаний всех детекторов было достаточно для однозначного определения места, в котором вы находитесь. Также нужно найти способ установить эти детекторы.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2\cdot 10^5$$$) — число мест для укрытия и число детекторов, которые уже есть у лорда Верити.

$$$i$$$-я из следующих $$$m$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — $$$i$$$-й детектор покрывает места от $$$l_i$$$ до $$$r_i$$$.

Гарантируется, что никакие два данных детектора не покрывают один и тот же отрезок мест для укрытия.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$, а сумма $$$m$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных сначала выведите одно целое число $$$k$$$ — минимальное число дополнительных детекторов.

Затем выведите $$$k$$$ строк. В $$$j$$$-й из них должны находиться два целых числа $$$u_j$$$ и $$$v_j$$$ ($$$1 \le u_j \le v_j \le n$$$), означающие, что $$$j$$$-й дополнительный детектор покрывает места для укрытия от $$$u_j$$$ до $$$v_j$$$.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
7
1 0
2 0
3 0
5 2
2 2
4 4
8 7
1 2
2 3
3 4
4 5
5 6
6 7
7 8
5 2
2 3
1 5
4 2
1 2
3 4
Выходные данные
0
1
1 1
2
1 1
2 2
2
1 3
1 1
0
2
1 4
1 2
1
2 3
Примечание

В первом наборе входных данных есть только одно место для укрытия, поэтому лорд Верити знает, что вы можете находиться только там. Детекторы не требуются.

Во втором наборе входных данных есть два возможных места для укрытия. Лорд Верити может установить один детектор с $$$u=v=1$$$, который сообщит, находитесь ли вы в позиции $$$1$$$. Поэтому по его показанию можно однозначно определить, находитесь вы в позиции $$$1$$$ или $$$2$$$.

В пятом наборе входных данных можно доказать, что лорд Верити может однозначно определить, в каком месте вы находитесь, используя только уже имеющиеся детекторы.