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 (Cr,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: (Ci,k=Cj,l); (Cj,k=Ci,l); (Ci,k \neq Cj,k). (Ci,k=Cj,l); (Cj,k=Ci,l); (Ci,k \neq Cj,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