首先发现无论如何操作，只有关于对角线对称的两个位置（）会被交换，而且只有和的操作会影响这两个位置的交换。 我们用来表示操作是否被执行，如果，我们不希望他们被交换所以我们希望，反之如果，我们希望他们交换所以我们希望。（代表按位异或）
对于字典序的问题，往往采用从前往后贪心的策略。对于当前的我们要看之前的限制是否允许我们希望的值。那么如何判断呢？我们用一种让并查集的边带权的技巧，即边的权值代表，那么一个分量中任意两点的异或值即为路径上边的异或值。为了方便实现我们用节点代表到其父节点的边。在find和join时要更新边权（见代码）。
条件就相当于给和中间连一条权值为的边，对应并查集的join操作，如果加边之前两个点不在同一个连通分量，那么条件一定是可以满足的。如果在同一个分量中，那么说明已经是确定的，如果说明当前条件不能满足，我们就跳过它。
其他实现细节见代码：
#include <bits/stdc++.h>
using namespace std;
struct UF {
vector<int> fa, sz, parity;
UF(int n) : fa(n), sz(n, 1), parity(n) { iota(fa.begin(), fa.end(), 0); }
array<int, 2> find(int x) {
if (fa[x] == x) {
return {x, 0};
}
auto [f, z] = find(fa[x]);
fa[x] = f;
parity[x] ^= z;
return {fa[x], parity[x]};
}
bool same(int x, int y) { return find(x) == find(y); }
bool join(int x, int y, int p) {
auto [fx, px] = find(x);
auto [fy, py] = find(y);
if (fx == fy)
return (px ^ py ^ p) == 0;
if (sz[fx] > sz[fy]) swap(fx, fy);
fa[fx] = fy;
parity[fx] = px ^ py ^ p;
sz[y] += sz[x];
return true;
}
};
void test_case() {
int n;
cin >> n;
vector a(n, vector(n, 0));
for (auto& v : a) {
for (auto& x : v) {
cin >> x;
}
}
UF uf(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i][j] == a[j][i]) {
continue;
}
if (uf.join(i, j, a[i][j] > a[j][i]) ^ (a[i][j] < a[j][i])) {
swap(a[i][j], a[j][i]);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << a[i][j] << " \n"[j == n - 1];
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
test_case();
}
}