C. AquaMoon и перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Cirno подготовила $$$n$$$ массивов длины $$$n$$$ каждый. Каждый массив — это перестановка из $$$n$$$ целых чисел от $$$1$$$ до $$$n$$$. Эти массивы специальные: для всех $$$1 \leq i \leq n$$$, если мы возьмем $$$i$$$-й элемент каждого массива и построим другой массив длины $$$n$$$, состоящий из этих элементов, получившийся массив также будет перестановкой $$$n$$$ чисел от $$$1$$$ до $$$n$$$. Другими словами, если эти $$$n$$$ массивов расположить друг под другом, образовав матрицу с $$$n$$$ строками и $$$n$$$ столбцами, эта матрица будет латинским квадратом.

После этого Cirno добавила дополнительные $$$n$$$ массивов, каждый массив также является перестановкой из $$$n$$$ целых чисел от $$$1$$$ до $$$n$$$. Для всех $$$1 \leq i \leq n$$$ существует хотя бы одна позиция $$$1 \leq k \leq n$$$, такая что для $$$i$$$-го и $$$(n + i)$$$-го массивов $$$k$$$-е элементы совпадают. Обратите внимание, что массивы с индексами от $$$n + 1$$$ до $$$2n$$$ не обязаны образовывать латинский квадрат.

Также Cirno убедилась, что среди $$$2n$$$ массивов никакие два не равны, то есть для всех пар индексов $$$1 \leq i < j \leq 2n$$$ существует хотя бы одна позиция $$$1 \leq k \leq n$$$, такая что в $$$i$$$-м и $$$j$$$-м массивах $$$k$$$-е элементы различны.

В конце Cirno произвольно поменяла порядок, в котором расположены подготовленные $$$2n$$$ массивов.

AquaMoon называет подмножество всех $$$2n$$$ массивов размера $$$n$$$ хорошим, если эти массивы образуют латинский квадрат.

AquaMoon хочет узнать, сколько хороших подмножеств существует. Поскольку это количество может быть очень большим, найдите его по модулю $$$998\,244\,353$$$. Также она хочет найти любое хорошее подмножество. Можете ли вы помочь ей?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных.

В первой строке описания каждого набора входных данных находится единственное целое число $$$n$$$ ($$$5 \leq n \leq 500$$$).

Затем $$$2n$$$ строк следует. $$$i$$$-я из этих строк содержит $$$n$$$ целых чисел, составляющих $$$i$$$-й массив.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$500$$$.

Выходные данные

Для каждого набора входных данных выведите две строки.

В первой строке выведите количество хороших подмножеств по модулю $$$998\,244\,353$$$.

Во второй строке выведите $$$n$$$ индексов от $$$1$$$ до $$$2n$$$ — индексы $$$n$$$ массивов, которые образуют хорошее подмножество (вы можете вывести их в любом порядке). Если существует несколько возможных ответов — выведите любой.

Пример
Входные данные
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
Выходные данные
1
1 2 3 4 5 6 7
2
1 3 5 6 10
4
1 3 6 7 8 9
Примечание

В первом наборе входных данных количество хороших подмножеств равно $$$1$$$. Единственное такое подмножество это подмножество массивов с индексами $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$7$$$.

Во втором наборе входных данных количество хороших подмножеств равно $$$2$$$. Эти подмножества это $$$1$$$, $$$3$$$, $$$5$$$, $$$6$$$, $$$10$$$, а также $$$2$$$, $$$4$$$, $$$7$$$, $$$8$$$, $$$9$$$.