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

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 \lt 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?

Cirno 准备了 $n$ 个长度均为 $n$ 的数组。每个数组都是 $1$ 到 $n$ 这 $n$ 个整数的一个排列。这些数组具有特殊性质：对所有 $1 \leq i \leq n$，若取每个数组的第 $i$ 个元素，并将它们组成一个长度为 $n$ 的新数组，则该新数组也是 $1$ 到 $n$ 这 $n$ 个整数的一个排列。换言之，若将这 $n$ 个数组纵向堆叠，构成一个 $n$ 行 $n$ 列的矩阵，则该矩阵是一个拉丁方。

随后，Cirno 额外添加了 $n$ 个数组，每个数组同样是 $1$ 到 $n$ 这 $n$ 个整数的一个排列。对于所有 $1 \leq i \leq n$，均存在至少一个位置 $1 \leq k \leq n$，使得第 $i$ 个数组与第 $(n + i)$-个数组在第 $k$ 个位置上的元素相同。注意：下标从 $n + 1$ 到 $2n$ 的这 $n$ 个数组本身不必构成拉丁方。

此外，Cirno 确保在全部 $2n$ 个数组中，任意两个数组互不完全相等；即对任意下标对 $1 \leq i < j \leq 2n$，均存在至少一个位置 $1 \leq k \leq n$，使得第 $i$ 个数组与第 $j$ 个数组在第 $k$ 个位置上的元素不同。

最后，Cirno 将这 $2n$ 个数组的顺序任意打乱。

AquaMoon 将大小为 $n$ 的数组子集称为“好”的，当且仅当这些数组构成一个拉丁方。

AquaMoon 想知道一共有多少个“好”子集。由于该数目可能非常大，请输出其对 $998\,244\,353$ 取模的结果。此外，她还希望找出任意一个“好”子集。你能帮她吗？

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

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$5 \leq n \leq 500$）。

随后是 $2n$ 行。其中第 $i$ 行包含 $n$ 个整数，表示第 $i$ 个数组。

保证所有测试用例的 $n$ 值之和不超过 $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.

对每个测试用例，输出两行。

第一行，输出好子集的数量对 $998\,244\,353$ 取模的结果。

第二行，输出 $n$ 个从 $1$ 到 $2n$ 的下标——即构成好子集的 $n$ 个数组的下标（可按任意顺序输出）。若存在多个可能的答案，输出任意一个即可。

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

在第一个测试用例中，好子集的数量为 $1$。唯一的好子集是索引为 $1$、$2$、$3$、$4$、$5$、$6$、$7$ 的数组构成的集合。

在第二个测试用例中，好子集的数量为 $2$。它们分别是 $1$、$3$、$5$、$6$、$10$ 或 $2$、$4$、$7$、$8$、$9$。