구성 알고리즘 실력을 끝까지 끌어올리겠다

BaoBao the Witch는 $n$행 $n$열 미로에 갇혀 있다. $i$행 $j$열 칸의 높이는 $h_{i,j}$이다. 미로에서 나가려면 모든 칸을 정확히 한 번씩 지나는 경로를 찾아야 한다. 이동할 수 있는 곳은 현재 칸과 변을 공유하는 인접한 칸뿐이다.

BaoBao는 매우 게으르다. 높이가 낮은 칸에서 높은 칸으로 올라갈 때마다 행복도가 떨어진다. 올라간 횟수가 내려간 횟수보다 많지 않도록 유효한 경로를 찾아라.

유효한 경로는 다음 조건을 만족하는 수열 $(x_1, y_1), (x_2, y_2), \ldots, (x_{n^2}, y_{n^2})$이다.

• 모든 $1 \le i \le n^2$에 대해 $1 \le x_i, y_i \le n$이다.
• 모든 $1 \le i, j \le n^2$에 대해 $i \ne j$이면 $(x_i, y_i) \ne (x_j, y_j)$이다.
• 모든 $2 \le i \le n^2$에 대해 $|x_i - x_{i-1}| + |y_i - y_{i-1}| = 1$이다.
• $\sum_{i=2}^{n^2} [h_{x_{i-1},y_{i-1}} < h_{x_i,y_i}] \le \sum_{i=2}^{n^2} [h_{x_{i-1},y_{i-1}} > h_{x_i,y_i}]$이다. 여기서 $[P]$는 $P$가 참이면 1, 거짓이면 0이다.

모든 칸의 높이는 $1$부터 $n^2$까지의 순열이므로, 유효한 경로를 따라 각 칸의 높이를 출력하기만 하면 된다.

여러 개의 테스트 케이스가 주어진다. 첫 줄에는 테스트 케이스의 개수 $T$ ($1 \le T \le 100$)가 주어진다.

각 테스트 케이스의 첫 줄에는 미로의 크기 $n$ ($2 \le n \le 64$)이 주어진다. 이어서 $n$개의 줄에 각각 $n$개의 정수 $h_{i,1}, h_{i,2}, \ldots, h_{i,n}$ ($1 \le h_{i,j} \le n^2$)이 주어진다. 입력의 모든 정수는 $n^2$의 순열을 이룬다.

각 테스트 케이스마다 한 줄에 $n^2$개의 정수를 공백으로 구분하여 출력한다. 정수는 유효한 경로의 순서대로 각 칸의 높이이다. 답이 여러 개이면 아무거나 출력해도 된다. 답은 항상 존재한다.