G2. Монотонные монохромные матрицы (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии ограничения на $$$n$$$ и $$$q$$$ очень большие. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Монохромная матрица размером $$$n \times n$$$ — это матрица из $$$n$$$ строк и $$$n$$$ столбцов, где каждая ячейка окрашена либо в чёрный, либо в белый цвет. Пусть цвет ячейки $$$(r,c)$$$ в монохромной матрице $$$C$$$ обозначается как $$$C[r,c]$$$.

Назовём такую матрицу $$$C$$$ монотонной, если она удовлетворяет следующему условию:

  • Не существует двух строк $$$1 \le i \lt j \le n$$$ и двух столбцов $$$1 \le k \lt l \le n$$$, которые удовлетворяют следующим трём условиям:
    • $$$C[i,k]=C[j,l]$$$;
    • $$$C[j,k]=C[i,l]$$$;
    • $$$C[i,k] \neq C[j,k]$$$.

Есть монохромная матрица $$$M$$$ размером $$$n \times n$$$, где все ячейки изначально белые. Пожалуйста, решите $$$q$$$ запросов следующего вида:

  • $$$r\;c$$$: Измените цвет ячейки $$$(r,c)$$$ в $$$M$$$ на чёрный. Затем определите, является ли $$$M$$$ монотонной или нет.

Для каждого запроса гарантируется, что цвет ячейки $$$(r,c)$$$ был белым до запроса.

Обратите внимание, что обновления являются постоянными. Другими словами, изменение цвета в одном запросе влияет на последующие запросы.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le \color{red}{2\,000\,000}$$$, $$$1 \le q \le \min(n^2,\color{red}{2\,000\,000})$$$).

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$r_i$$$, $$$c_i$$$, обозначающие $$$i$$$-й запрос ($$$1 \le r_i,c_i \le n$$$).

Для каждого запроса гарантируется, что цвет ячейки $$$(r,c)$$$ был белым до запроса.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$\color{red}{2\,000\,000}$$$.

Гарантируется, что сумма $$$q$$$ по всем наборам входных данных не превосходит $$$\color{red}{2\,000\,000}$$$.

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

Для каждого запроса выведите «YES» или «NO» на отдельной строке в зависимости от ответа на запрос.

Вы можете выводить ответ в любом регистре. Например, строки «yEs», «yes», и «Yes» также будут распознаны как положительные ответы.

Пример
Входные данные
2
3 9
2 2
3 3
2 3
3 1
3 2
1 1
1 2
2 1
1 3
5 17
2 1
4 5
4 1
3 3
3 1
3 5
1 3
1 5
1 1
5 3
5 5
5 1
1 4
5 2
5 4
1 2
2 5
Выходные данные
YES
NO
YES
NO
YES
NO
NO
YES
YES
YES
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
YES
YES
NO
YES
YES
YES
Примечание

В первом наборе входных данных $$$M$$$ имеет размер $$$3 \times 3$$$. Состояния $$$M$$$ после каждого запроса показаны ниже.

$$$$$$\quad\, \begin{bmatrix} \square & \square & \square\\ \square & \blacksquare & \square\\ \square & \square & \square \end{bmatrix} \to \begin{bmatrix} \square & \square & \square\\ \square & \color{red}{\blacksquare} & \color{red}{\square}\\ \square & \color{red}{\square} & \color{red}{\blacksquare} \end{bmatrix} \to \begin{bmatrix} \square & \square & \square\\ \square & \blacksquare & \blacksquare\\ \square & \square & \blacksquare \end{bmatrix} \\\to \begin{bmatrix} \square & \square & \square\\ \color{red}{\square} & \color{red}{\blacksquare} & \blacksquare\\ \color{red}{\blacksquare} & \color{red}{\square} & \blacksquare \end{bmatrix} \to \begin{bmatrix} \square & \square & \square\\ \square & \blacksquare & \blacksquare\\ \blacksquare & \blacksquare & \blacksquare \end{bmatrix} \to \begin{bmatrix} \color{red}{\blacksquare} & \color{red}{\square} & \square\\ \color{red}{\square} & \color{red}{\blacksquare} & \blacksquare\\ \blacksquare & \blacksquare & \blacksquare \end{bmatrix} \\\to \begin{bmatrix} \color{red}{\blacksquare} & \blacksquare & \color{red}{\square}\\ \color{red}{\square} & \blacksquare & \color{red}{\blacksquare}\\ \blacksquare & \blacksquare & \blacksquare \end{bmatrix} \to \begin{bmatrix} \blacksquare & \blacksquare & \square\\ \blacksquare & \blacksquare & \blacksquare\\ \blacksquare & \blacksquare & \blacksquare \end{bmatrix} \to \begin{bmatrix} \blacksquare & \blacksquare & \blacksquare\\ \blacksquare & \blacksquare & \blacksquare\\ \blacksquare & \blacksquare & \blacksquare \end{bmatrix}$$$$$$

На запросах, где $$$M$$$ не монотонна, четыре выделенные красным квадрата обозначают ячейки, которые нарушают указанное выше условие.