大小为的数码问题，两个局面可达，结论：
  1. 当为奇数时，当且仅当两个局面下网格中的数依次写成行n\times m - 1个元素的序列后（不考虑空格），逆序对个数的奇偶性相同
  2. 当为偶数时，当且仅当两个局面下网格中的数依次写成行n\times m - 1个元素的序列后（不考虑空格），“逆序对数之差”和“两个局面下空格所在行数之差”奇偶性相同
所以就是归并排序求逆序对


总代码：
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 502 * 502;

int n, a[N], b[N], a1[N], b1[N];
int sum1, sum2;


void quick_sort_a(int l, int r){
    if(l >= r) return;
    int mid = (l + r) / 2;
    quick_sort_a(l, mid);
    quick_sort_a(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) a1[k ++] = a[i ++];
        else{
            a1[k ++] = a[j ++];
            sum1 += mid - i + 1;
        }
    }
    while(i <= mid) a1[k ++] = a[i ++];
    while(j <= r) a1[k ++] = a[j ++];
    for(int i = l; i <= r; i ++) a[i] = a1[i];
}

void quick_sort_b(int l, int r){
    if(l >= r) return;
    int mid = (l + r) / 2;
    quick_sort_b(l, mid);
    quick_sort_b(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r){
        if(b[i] <= b[j]) b1[k ++] = b[i ++];
        else{
            b1[k ++] = b[j ++];
            sum2 += mid - i + 1;
        }
    }
    while(i <= mid) b1[k ++] = b[i ++];
    while(j <= r) b1[k ++] = b[j ++];
    for(int i = l; i <= r; i ++) b[i] = b1[i];
}
void solve(){

    while(cin >> n){
        sum1 = sum2 = 0;
        int idx = 0;
        for(int i = 1; i <= n * n; i ++){
            int x; cin >> x;
            if(x) a[++ idx] = x;
        }
        idx = 0;
        for(int i = 1; i <= n * n; i ++){
            int x; cin >> x;
            if(x) b[++ idx] = x;
        }
        quick_sort_a(1, n * n - 1);
        quick_sort_b(1, n * n - 1);
        if((sum1 & 1) == (sum2 & 1)) cout << "TAK" << endl;
        else cout << "NIE" << endl;
    } 
    return ;
}

signed main(){
    HelloWorld;
    
    int tt = 1; 
    while(tt --) solve();
    return 0;
}