AquaMoon and Permutations

time limit per test: 2 seconds

memory limit per test: 256 megabytes

Articles

Cirno has prepared $n$ arrays of length $n$ each. Each array is a permutation of $n$ integers from $1$ to $n$. These arrays are special: for all $1≤i≤n$, if we take the $i$-th element of each array and form another array of length $n$ with these elements, the resultant array is also a permutation of $n$ integers from $1$ to $n$. In the other words, if you put these $n$ arrays under each other to form a matrix with $n$ rows and nn columns, this matrix is a Latin square.

Afterwards, Cirno added additional $n$ arrays, each array is a permutation of $n$ integers from 11 to $n$. For all $1≤i≤n$, there exists at least one position $1≤k≤n$, such that for the $i$-th array and the $(n+i)$-th array, the $k$-th element of both arrays is the same. Notice that the arrays indexed from $n+1$ to $2n$ don’t have to form a Latin square.

Also, Cirno made sure that for all $2n$ arrays, no two arrays are completely equal, i. e. for all pair of indices $1≤i<j≤2n$, there exists at least one position $1≤k≤n$, such that the $k$-th elements of the $i$-th and $j$-th array are different.

Finally, Cirno arbitrarily changed the order of $2n$ arrays.

AquaMoon calls a subset of all $2n$ arrays of size $n$ good if these arrays from a Latin square.

AquaMoon wants to know how many good subsets exist. Because this number may be particularly large, find it modulo $998244353$. Also, she wants to find any good subset. Can you help her?

Input

The input consists of multiple test cases. The first line contains a single integer $t (1≤t≤100)$ — the number of test cases.

The first line of each test case contains a single integer $n (5≤n≤500)$.

Then $2n$ lines followed. The $i$-th of these lines contains $n$ integers, representing the $i$-th array.

It is guaranteed, that the sum of $n$ over all test cases does not exceed $500$.

Output

For each test case print two lines.

In the first line, print the number of good subsets by modulo $998244353$.

In the second line, print $n$ indices from $1$ to $2n$ — indices of the $n$ arrays that form a good subset (you can print them in any order). If there are several possible answers — print any of them.

Example

input

3
7
1 2 3 4 5 6 7
2 3 4 5 6 7 1
3 4 5 6 7 1 2
4 5 6 7 1 2 3
5 6 7 1 2 3 4
6 7 1 2 3 4 5
7 1 2 3 4 5 6
1 2 3 4 5 7 6
1 3 4 5 6 7 2
1 4 5 6 7 3 2
1 5 6 7 4 2 3
1 6 7 5 2 3 4
1 7 6 2 3 4 5
1 7 2 3 4 5 6
5
4 5 1 2 3
3 5 2 4 1
1 2 3 4 5
5 2 4 1 3
3 4 5 1 2
2 3 4 5 1
1 3 5 2 4
4 1 3 5 2
2 4 1 3 5
5 1 2 3 4
6
2 3 4 5 6 1
3 1 2 6 4 5
6 1 2 3 4 5
5 6 1 3 2 4
4 3 6 5 2 1
5 6 1 2 3 4
4 5 6 1 2 3
3 4 5 6 1 2
1 2 3 4 5 6
2 5 4 1 6 3
3 2 5 4 1 6
1 4 3 6 5 2

output

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

Node

In the first test case, the number of good subsets is 1. The only such subset is the set of arrays with indices 1, 2, 3, 4, 5, 6, 7.

In the second test case, the number of good subsets is 2. They are 1, 3, 5, 6, 10 or 2, 4, 7, 8, 9.

Tutorial

Among all the arrays not be chosen, if an array have a number which appears exactly once at its column, that the array must belong to the n original arrays. So, we can choose the array and delete all arrays have at least one same bit with it.

If there not exists such an array discribed above, according to the Pigeonhole Principle, all numbers of the unchosen arrays must appear exactly twice on their columns. It means either the original arrays or the additional arrays can form a correct latin square. So, it’s correct to choose any one of the unchosen array and delete all arrays have at least one same bit with it. Meanwhile, we need to multiply the number of solutions by 2.

We need to repeat the above operations, until we have chosen n arrays.

code

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+1;
const int mod = 998244353;
int a[1001][501], b[501], cnt[501];
int f[1001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1; 
    cin >> T;
    while(T --) {
        int n;
        cin >> n;
        for(int i = 1; i <= 2*n; ++ i) {
            for(int j = 1; j <= n; ++ j) {
                cin >> a[i][j];
            }   
        }
        for(int i = 0; i <= 2*n; ++ i) {
            f[i] = i+1;
        }
        f[2*n] = 0;

        long long ans = 1;
        for(int i = 1; i <= n; ++ i) {
            int id = 0, flag = false;
            for(int j = 1; j <= n; ++ j) {
                memset(cnt, 0, sizeof cnt);
                for(int k = 0; f[k]; k = f[k]) {
                    cnt[a[f[k]][j]] ++;
                }
                int val = -1;
                for(int k = 1; k <= n; ++ k) {
                    if (cnt[k] == 1) {
                        val = k;
                        break;
                    }
                }
                if (val == -1) continue;
                for(int k = 0; f[k]; k = f[k]) {
                    if (a[f[k]][j] == val) {
                        id = k;
                        break;
                    }
                }
                flag = true;
                break;
            }    
            if (!flag) ans = ans * 2 % mod;
            b[i] = f[id];
            f[id] = f[f[id]];
            for(int j = 1; j <= n; ++ j) {
                for(int k = 0; f[k];) {
                    if (a[b[i]][j] == a[f[k]][j]) {
                        f[k] = f[f[k]];
                    }
                    else k = f[k];
                }
            }

        }
        cout << ans << "\n";
        for(int i = 1; i <= n; ++ i) {
            cout << b[i] << " \n"[i==n];
        }
    }
    return 0;
}