CF2201F2 Monotone Monochrome Matrices (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, the constraints on $ n $ and $ q $ are very large. You can hack only if you solved all versions of this problem. A monochrome matrix of size $ n \times n $ is a matrix of $ n $ rows and $ n $ columns, where each cell is colored either black or white. Let the color of cell $ (r,c) $ in a monochrome matrix $ C $ be denoted as $ C[r,c] $ . Let's call such a matrix $ C $ monotone if it satisfies the following condition: - There exist no two rows $ 1 \le i \lt j \le n $ and two columns $ 1 \le k \lt l \le n $ that satisfy the following three conditions: - $ C[i,k]=C[j,l] $ ; - $ C[j,k]=C[i,l] $ ; - $ C[i,k] \neq C[j,k] $ . There is a monochrome matrix $ M $ of size $ n \times n $ , where all cells are initially white. Please solve $ q $ queries of the following kind: - $ r\;c $ : Change the color of the cell $ (r,c) $ in $ M $ to black. Then, determine if $ M $ is monotone or not. For each query, it is guaranteed that the color of the cell $ (r,c) $ was white before the query. Do note that the updates are persistent. In other words, the change in color from one query affects the later queries as well.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^3 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ q $ ( $ 2 \le n \le \color{red}{2\,000\,000} $ , $ 1 \le q \le \min(n^2,\color{red}{2\,000\,000}) $ ). Each of the $ q $ following lines contains two integers $ r_i $ , $ c_i $ denoting the $ i $ -th query ( $ 1 \le r_i,c_i \le n $ ). For each query, it is guaranteed that the color of the cell $ (r,c) $ was white before the query. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ \color{red}{2\,000\,000} $ . It is guaranteed that the sum of $ q $ over all test cases does not exceed $ \color{red}{2\,000\,000} $ .

For each query, output "YES" or "NO" on a separate line based on the answer of the query. You can output the answer in any case. For example, the strings "yEs", "yes", and "Yes" will also be recognized as positive responses.

In the first test case, $ M $ has size $ 3 \times 3 $ . The states of $ M $ after each query are as shown below. $$$ \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} $$$ On queries where $ M $ is not monotonic, the four squares highlighted in red denote cells that violate the condition stated above.