P8416 [THUPC 2022 Final] Save or Destroy

*Some say it saved the world; others say it destroyed the world.* This world is on the brink of collapse! Order has already fallen into chaos. Order can be abstracted as an $n \times n$ matrix containing a permutation of $1 \sim n^2$. You want to save the world, so you ask God to help restore order. However, God is not all-powerful: it can only swap two numbers in the same row or in the same column of the matrix. Also, it does not know how to swap to restore the matrix and must follow your instructions. Fortunately, you do not have to restore it using the minimum number of swaps. You only need to be no worse than the worst case. That is, if your number of swaps is $k$, and among all permutations of $1 \sim n^2$, the maximum value of the minimum required swaps is $k_0$, then you only need to satisfy $k \le k_0$. Note: restoring means turning the matrix into the following matrix: $\begin{matrix} 1 & 2 & 3 & \cdots & n \\ n+1 & n+2 & n+3 & \cdots & 2n \\ 2n+1 & 2n+2 & 2n+3 & \cdots & 3n\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ (n-1)n+1 & (n-1)n+2 & (n-1)n+3 & \cdots & n^2 \end{matrix}$

The next $n$ lines each contain $n$ positive integers, describing this $n \times n$ matrix. It is guaranteed that each number in $1 \sim n^2$ appears exactly once.

The first line contains a non-negative integer $k$, which is your number of swaps. The next $k$ lines each contain four positive integers $x_1, y_1, x_2, y_2$, meaning you swap the number at row $x_1$, column $y_1$ with the number at row $x_2$, column $y_2$. You must guarantee that $x_1 = x_2$ or $y_1 = y_2$.

[Sample 1 Explanation] It can be proven that this is one of the solutions with the minimum number of swaps, and obviously it meets the requirement. [Sample 2 Explanation] For this input, the plan in the sample output does not use the minimum number of swaps. However, we know there exists a permutation of $1 \sim n^2$ (namely, the previous sample) that needs at least $3$ swaps, so this plan is also valid. [Sample 3 Explanation] We allow the case where $(x_1, y_1) = (x_2, y_2)$. [Sample 4 Explanation] Note that $k$ can be equal to $0$. [Constraints and Notes] It is guaranteed that $1 \le n \le 1000$. It is guaranteed that each number in $1 \sim n^2$ appears exactly once in the input matrix. Translated by ChatGPT 5