Future Dominators
Contest: Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: graphs, greedy

Dhruvil and amenotiomoi are sitting in different countries and chatting online. Initially, amenotiomoi has an empty board of size $$$n \times n$$$, and Dhruvil has a sequence of integers $$$1, 2, \ldots, n^2$$$, each number occurring exactly once. The numbers may be placed in the cells of the board, each cell is either empty or contains exactly one number.

The current state of the board is called good, if there is a way of placing the remaining numbers in empty cells so that all numbers except $$$1$$$ have a neighbor with a smaller value. Two cells are neighbors if they share an edge.

The rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, the columns are numbered from $$$1$$$ to $$$n$$$ from left to right. The cell at the intersection of the $$$x$$$-th row and the $$$y$$$-th column is denoted as $$$(x, y)$$$.

To chat, amenotiomoi asks $$$q$$$ queries to Dhruvil. Each time he provides Dhruvil with an empty cell $$$(x, y)$$$. Dhruvil has to place one of the remaining numbers in this cell so that the board is still good. Among all ways to do this, he chooses the largest possible number he can place and sends this number to amenotiomoi as the answer to the query.

Since amenotiomoi knows the correct answer every time, he tells Dhruvil $$$(x \oplus k,y \oplus k)$$$ instead of $$$(x, y)$$$, where $$$k$$$ is the answer for the previous query. If amenotiomoi is sending the first query, he considers $$$k = 0$$$. Each time Dhruvil has to decode the query and send the answer to amenotiomoi. Here $$$\oplus$$$ denotes the bitwise XOR operation.

Help Dhruvil reply to all amenotiomoi's queries.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 10^3$$$, $$$1 \le q \le n^2$$$).

The $$$i$$$-th of the following $$$q$$$ lines contains two integers $$$x_i'$$$ and $$$y_i'$$$. The corresponding cell is $$$(x_i, y_i)$$$, where $$$x_i'=x_i \oplus k$$$ and $$$y_i' = y_i \oplus k$$$, where $$$k$$$ is the correct answer for the previous query. If $$$i = 1$$$, then $$$k = 0$$$ is used. It is guaranteed that $$$1 \le x_i, y_i \le n$$$ and that $$$(x_i, y_i)$$$ is an empty cell at the moment of $$$i$$$-th query.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, output one line, containing the answers to all queries, separated by spaces.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the first query is $$$(1, 1)$$$, Dhruvil puts $$$4$$$ in that cell.

The second query is $$$(6, 6)$$$, Dhruvil decode it as $$$(2, 2)$$$ using the previous answer ($$$2 \oplus 4 = 6$$$). If Dhruvil places $$$3$$$ to the cell $$$(2, 2)$$$, the board stops being good. So, Dhruvil places $$$2$$$ in this cell.

The third query is $$$(3, 0)$$$, Dhruvil decodes it as $$$(1, 2)$$$ using the previous answer ($$$1 \oplus 2 = 3$$$, $$$2 \oplus 2 = 0$$$). Dhruvil can place $$$3$$$ in this cell.

The fourth query is $$$(1, 2)$$$, Dhruvil decodes it as $$$(2, 1)$$$ using the previous answer ($$$2 \oplus 3 = 1$$$, $$$1 \oplus 3 = 2$$$). Now, only $$$1$$$ remains in the sequence, and after Dhruvil places $$$1$$$ in this cell, the board becomes full and remains good.

Here you can see the entire history of the board:

In the second test case, the final state of the board is:

$$$8$$$$$$7$$$$$$5$$$$$$9$$$$$$3$$$$$$4$$$$$$1$$$$$$2$$$$$$6$$$

Example input:
3
2 4
1 1
6 6
3 0
1 2
3 9
2 1
8 11
4 4
4 4
2 0
4 4
11 10
1 3
3 2
1 1
1 1

Example output:
4 2 3 1 
9 7 6 3 5 8 2 1 4 
1

Editorial:
This problem is based on a method of online edge deletion and querying connectivity of a planar graph.
Firstly, if this vertex is not an articulation point, it will not cause any change in connectivity. Therefore, the algorithm needs to determine whether a certain vertex is an articulation point.
Thinking about using a data structure called union-find to keep track of the deleted points, we can identify a clear condition: if a vertex has two neighbors with the same union-find value among its $$$8$$$-connected neighbors, then it becomes an articulation point. This is easy to understand:
When the values in the union-find are the same, it means there's a loop forming, and this messes up how things are connected inside and outside the loop. But if all the values in the union-find are different, no loops will form, and we can find a way to connect these points to each other.
For points which are not articulation points, the greedy way to do it is to put the biggest number in the component of points that are already connected. This helps keep things organized and efficient.
Now, let's think about the case of articulation points. If we've already decided to put a $$$1$$$ in the connected group before the articulation point, it's pretty clear that, in order to get the largest overall value, we should put the $$$1$$$ in the smallest connected component. And the remaining connected components will then share the largest value. In other words, when we pick the largest number for one component, the largest numbers for the other components will decrease at the same time.
If we're sure that a particular component won't have the number $$$1$$$ placed in it, then the point we're looking at can only hold the value which is one more than the maximum value in the connected component formed by removing this point. It might sound a bit complicated, but I'll show you a picture to make it clearer.
In simpler words, the value we put in that point is fixed. It's just the right amount to make sure it matches the sum of all the values in the connected group above it, instead of picking the smallest group. To make this work, we have to keep track of where the smallest value is located inside that connected component.
The method we discussed is quite slow, around $$$O(n^3)$$$. Now, let's talk about how to make it much faster, around $$$O(n^2 log n)$$$.
Firstly, for every cell, we keep a pointer that points to the information about its connected component. So, whenever we update any cell, the entire connected component gets updated automatically.
When dealing with articulation points, it's important to quickly update the pointer information. One effective way is to use a clever merging technique. This involves simultaneously performing a breadth-first search on multiple connected components. If only one connected component remains incomplete in the search, we immediately stop all calculations.
One of the things we need to do is to launch the BFS from the new connected components which arise after fixing a certain cell. In particular, we don't want to launch two parallel BFS which start in different cells but sooner or later are merged into one component. So among the $$$4$$$ side-neighbors of the cell being fixed, we need to segregate them based on the remaining connectivity, considering the removal of the current cell. To facilitate this segregation, we examine the 8 corner- or side-neighbors and analyze their DSU values. For instance, if all these DSU values are distinct from each other, it implies that the empty neighboring cells belong to a unified component.
Conversely, if certain DSU values occur multiple times, it signifies the existence of a planar cycle that becomes linked through the cell being fixed. Consequently, cells within and outside this cycle must be assigned to separate connected components. To manage this, we iterate through pairs of $$$8-$$$neighbors sharing the same DSU value and classify the $$$4-$$$neighbors into those situated within the cycle and those outside it.
During the pointer update process, we handle smaller connected components by updating their pointers in a straightforward manner. For larger connected components, we retain their original pointers and make necessary adjustments. It's easy to show that this approach updates pointers efficiently (each time a connected group is encountered in the search, its size at least doubles). This helps us achieve a time complexity of $$$O(n^2 log n)$$$.
Next, we also need to determine whether two cells are part of the same connected component. This is necessary for calculating the situation represented in the previous image. This step is quite simple because we ensured earlier that pointers of different connected components are always different. So, all we need to do is compare the pointer values to check if two cells belong to the same connected component.
For the connected components that share the largest value, there are several ways to handle them. One approach is to use the '*int' data type for the maximum value, so changing one value directly changes the shared value. Another method is to use a 'vector' to store the pointers that share the value, and when updating, you iterate through this vector to update them.
It's easy to prove that the maximum shared values can only exist in a maximum of $$$O(1)$$$ components simultaneously. This is because they only arise when cutting an articulation point in a connected component where the value is not $$$1$$$, and these components cannot merge together.
So, the total time complexity will be $$$O(n^2logn)$$$.