Codeforces Round 732 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

2-sat

brute force

combinatorics

constructive algorithms

graph matchings

graphs

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. AquaMoon and Permutations

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputCirno 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 < 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?

Input

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

Output

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.

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

Note

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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/09/2023 07:38:09 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|