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

Вам дана бинарная матрица $$$b$$$ (все элементы матрицы равны $$$0$$$ или $$$1$$$) из $$$n$$$ строк и $$$n$$$ столбцов.

Вам нужно построить $$$n$$$ множеств $$$A_1, A_2, \ldots, A_n$$$, для которых выполняются следующие условия:

  • Каждое множество непустое и состоит из различных целых чисел от $$$1$$$ до $$$n$$$ включительно.
  • Все множества попарно различны.
  • Для всех пар $$$(i,j)$$$, удовлетворяющих условиям $$$1\leq i, j\leq n$$$, $$$b_{i,j}=1$$$ тогда и только тогда, когда $$$A_i\subsetneq A_j$$$. Другими словами, $$$b_{i, j}$$$ равно $$$1$$$, если $$$A_i$$$ является собственным подмножеством $$$A_j$$$ и $$$0$$$ в противном случае.

Множество $$$X$$$ является собственным подмножеством множества $$$Y$$$, если $$$X$$$ является непустым подмножеством $$$Y$$$, и $$$X \neq Y$$$.

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

Если существует несколько решений, то можно вывести любое из них.

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка содержит целое число $$$n$$$ ($$$1\le n\le 100$$$).

Следующие $$$n$$$ строк содержат бинарную матрицу $$$b$$$, $$$j$$$-е символ $$$i$$$-й строки обозначает $$$b_{i,j}$$$.

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

Гарантируется, что для всех наборов входных данных в данной задаче такие $$$n$$$ множеств существуют.

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

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

В $$$i$$$-й строке сначала выведите $$$s_i$$$ $$$(1 \le s_i \le n)$$$  — размер множества $$$A_i$$$. Затем выведите $$$s_i$$$ попарно различных целых чисел от $$$1$$$ до $$$n$$$  — элементы множества $$$A_i$$$.

Если существует несколько решений, то можно вывести любое из них.

Гарантируется, что для всех наборов входных данных в данной задаче такие $$$n$$$ множеств существуют.

Пример
Входные данные
2
4
0001
1001
0001
0000
3
011
001
000
Выходные данные
3 1 2 3
2 1 3
2 2 4
4 1 2 3 4
1 1
2 1 2
3 1 2 3
Примечание

В первом наборе входных данных имеем $$$A_1 = \{1, 2, 3\}, A_2 = \{1, 3\}, A_3 = \{2, 4\}, A_4 = \{1, 2, 3, 4\}$$$. Множества $$$A_1, A_2, A_3$$$ являются собственными подмножествами $$$A_4$$$, а также множество $$$A_2$$$ является собственным подмножеством $$$A_1$$$. Никакое другое множество не является собственным подмножеством никакого другого множества.

Во втором наборе входных данных имеем $$$A_1 = \{1\}, A_2 = \{1, 2\}, A_3 = \{1, 2, 3\}$$$. $$$A_1$$$ является собственным подмножеством $$$A_2$$$ и $$$A_3$$$, а $$$A_2$$$ является собственным подмножеством $$$A_3$$$.