A14450. AquaMoon and Permutations

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 \leq i \leq 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 $n$ columns, this matrix is a [Latin square](https://en.wikipedia.org/wiki/Latin_square).

Afterwards, Cirno added additional $n$ arrays, each array is a permutation of $n$ integers from $1$ to $n$ . For all $1 \leq i \leq n$ , there exists at least one position $1 \leq k \leq 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 \leq i < j \leq 2n$ , there exists at least one position $1 \leq k \leq 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 $998\,244\,353$ . Also, she wants to find any good subset. Can you help her?

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

The first line of each test case contains a single integer $n$ ( $5 \leq n \leq 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$ .

For each test case print two lines.

In the first line, print the number of good subsets by modulo $998\,244\,353$ .

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.

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$ .