You are given a binary matrix $b$ (all elements of the matrix are $0$ or $1$) of $n$ rows and $n$ columns.

You need to construct a $n$ sets $A_1, A_2, \ldots, A_n$, for which the following conditions are satisfied:

Each set is nonempty and consists of distinct integers between $1$ and $n$ inclusive.

All sets are distinct.

For all pairs $(i,j)$ satisfying $1\leq i, j\leq n$, $b_{i,j}=1$ if and only if $A_i\subsetneq A_j$. In other words, $b_{i, j}$ is $1$ if $A_i$ is a proper subset of $A_j$ and $0$ otherwise.

Set $X$ is a proper subset of set $Y$, if $X$ is a nonempty subset of $Y$, and $X \neq Y$.

It's guaranteed that for all test cases in this problem, such $n$ sets exist. Note that it doesn't mean that such $n$ sets exist for all possible inputs.

If there are multiple solutions, you can output any of them.


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1\le t\le 1000$) — the number of test cases. The description of test cases follows.

The first line contains a single integer $n$ ($1\le n\le 100$).

The following $n$ lines contain a binary matrix $b$, the $j$-th character of $i$-th line denotes $b_{i,j}$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.

It's guaranteed that for all test cases in this problem, such $n$ sets exist.


-----Output-----

For each test case, output $n$ lines.

For the $i$-th line, first output $s_i$ $(1 \le s_i \le n)$  — the size of the set $A_i$. Then, output $s_i$ distinct integers from $1$ to $n$  — the elements of the set $A_i$.

If there are multiple solutions, you can output any of them.

It's guaranteed that for all test cases in this problem, such $n$ sets exist.


-----Examples-----

Input
2
4
0001
1001
0001
0000
3
011
001
000
Output
3 1 2 3
2 1 3
2 2 4
4 1 2 3 4
1 1
2 1 2
3 1 2 3


-----Note-----

In the first test case, we have $A_1 = \{1, 2, 3\}, A_2 = \{1, 3\}, A_3 = \{2, 4\}, A_4 = \{1, 2, 3, 4\}$. Sets $A_1, A_2, A_3$ are proper subsets of $A_4$, and also set $A_2$ is a proper subset of $A_1$. No other set is a proper subset of any other set.

In the second test case, we have $A_1 = \{1\}, A_2 = \{1, 2\}, A_3 = \{1, 2, 3\}$. $A_1$ is a proper subset of $A_2$ and $A_3$, and $A_2$ is a proper subset of $A_3$.

Difficulty: MEDIUM
Tags: Greedy algorithms

Graph algorithms

Graph traversal

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
t = int(input())

def solve():
	n = int(input())
	res = [[] for _ in range(n)]
	for i in range(n):
		s = input()
		res[i].append(i + 1)
		for (j, c) in enumerate(s):
			if c == '1':
				res[j].append(i + 1)
	for x in res:
		print(len(x), end=' ')
		print(' '.join(map(str, x)))
for i in range(t):
	solve()


def construct_sets(M, n):
	set_L = []
	for i in range(1, n + 1):
		set_L.append([str(i)])
	for i in range(n):
		for j in range(n):
			if M[i][j] == 1:
				set_L[j].append(str(i + 1))
	return set_L

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		M = []
		for j in range(n):
			A = list(input())
			M.append([int(A[i]) for i in range(n)])
		set_L = construct_sets(M, n)
		for i in range(n):
			print(str(len(set_L[i])) + ' ' + ' '.join(set_L[i]))
main()


def solution():
	n = int(input())
	graph = [set([i]) for i in range(n + 1)]
	i = 1
	while i <= n:
		row = [int(j) for j in list(input())]
		for (j, val) in enumerate(row):
			if val:
				graph[j + 1].add(i)
		i += 1
	for i in range(1, n + 1):
		ans = str(len(graph[i]))
		for ele in graph[i]:
			ans += ' ' + str(ele)
		print(ans)
num = int(input())
while num:
	solution()
	num -= 1


I = input
for _ in [0] * int(I()):
	r = range(int(I()))
	i = 0
	for x in zip(*(I() for i in r)):
		i += 1
		x = (i, *(j + 1 for j in r if '0' < x[j]))
		print(len(x), *x)


t = int(input())
for _ in range(t):
	n = int(input())
	r = [[i + 1] for i in range(n)]
	for i in range(n):
		s = str(input())
		for j in range(n):
			if s[j] == '1':
				r[j].append(i + 1)
	for i in range(n):
		print(len(r[i]), *r[i])


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]

def solve():
	n = ni()
	mat = []
	for l in range(n):
		mat.append(list(map(int, list(INP()))))
	out = [[] for _ in range(n)]
	for i in range(n):
		out[i].append(i + 1)
		for j in range(n):
			if mat[i][j] == 1 and i != j:
				out[j].append(i + 1)
	for l in out:
		print(len(l), ' '.join(map(str, l)))
t = ni()
for case in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	mat = [[i + 1] for i in range(n)]
	for i in range(n):
		a = input()
		for j in range(n):
			if a[j] == '1':
				mat[j].append(i + 1)
	for i in range(n):
		print(len(mat[i]), *mat[i])


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = [list(inp()) for i in range(n)]
	ans = [None] * n

	def getans(i):
		if ans[i]:
			return ans[i]
		v = {i + 1}
		for j in range(n):
			if a[j][i] == '1':
				v |= getans(j)
		ans[i] = v
		return v
	for i in range(n):
		v = getans(i)
		print(len(v), ' '.join(map(str, v)))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import math
import collections
import bisect
import heapq
from collections import deque
from math import sqrt, ceil, floor

def inp_arr():
	return list(map(int, input().strip().split(' ')))

def inp_str_arr():
	return list(input().strip().split(' '))

def inp_str():
	return input()

def solve():
	(n,) = inp_arr()
	a = []
	for i in range(n):
		s = inp_str()
		a.append(s)
	ans = [[i + 1] for i in range(n)]
	for i in range(n):
		for j in range(n):
			if a[i][j] == '1':
				ans[j].append(i + 1)
	for x in ans:
		print(len(x), end=' ')
		x.sort()
		for y in x:
			print(y, end=' ')
		print('')
(tt,) = inp_arr()
for t in range(tt):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = [[] for __ in range(n + 1)]
	for i in range(1, n + 1):
		a[i].append(i)
		for (j, c) in zip(list(range(1, n + 1)), list(input())):
			if c == '1':
				a[j].append(i)
	for i in range(1, n + 1):
		print(len(a[i]), *a[i])


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		sets = [{i} for i in range(1, n + 1)]
		for i in range(n):
			a = list(map(int, input()))
			for j in range(n):
				if a[j] == 1:
					sets[j].update(sets[i])
		for i in range(n):
			print(len(sets[i]), *sets[i])
main()


import math
for _ in range(int(input())):
	n = int(input())
	s = [''] * n
	for i in range(n):
		s[i] = input()
	ans = [set() for i in range(n)]
	for i in range(n):
		ans[i].add(i + 1)
		for j in range(n):
			if s[i][j] == '1':
				ans[j].add(i + 1)
	for i in range(n):
		print(len(ans[i]), *ans[i])


t = int(input())
while t:
	n = int(input())
	s = []
	for i in range(n):
		s.append(input())
	a = [set() for i in range(n)]
	for i in range(n):
		a[i].add(i + 1)
		for j in range(n):
			if s[i][j] == '1':
				a[j].add(i + 1)
	for i in a:
		print(len(i), end=' ')
		print(*i, end=' ')
		print()
	t -= 1


I = lambda : int(input())
Is = lambda : map(int, input().split())
Li = lambda : list(map(int, input().split()))

def solve():
	n = I()
	ans = []
	for x in range(1, n + 1):
		ans.append({x})
	for i in range(n):
		a = input()
		for j in range(n):
			if a[j] == '1':
				ans[j].add(i + 1)
	for i in ans:
		print(len(i), *i)
	return 1
t = I()
while t:
	solve()
	t -= 1


import sys
input = sys.stdin.readline
from random import randint
RANDOM = randint(1, 10 ** 9)

class myHash(int):

	def __init__(self, x):
		int.__init__(x)

	def __hash__(self):
		return super(myHash, self).__hash__() ^ RANDOM

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	n = readInt()
	ans = [[True] * n for _ in range(n)]
	for i in range(n):
		s = readStr()
		for j in range(n):
			if i != j and s[j] == '0':
				ans[j][i] = False
	for each in ans:
		tmp = []
		for i in range(n):
			if each[i]:
				tmp.append(i + 1)
		print(*[len(tmp)] + tmp)
	return
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	for i in range(n):
		M = [[i + 1] for i in range(n)]
	for j in range(n):
		s = input()
		for k in range(n):
			if s[k] == '1':
				M[k].append(j + 1)
	for b in M:
		print(len(b), *b)


for t in range(int(input())):
	n = int(input())
	num_list = []
	for i in range(n):
		s = input()
		num_list.append(s)
	ans = [set() for i in range(n)]
	for i in range(n):
		ans[i].add(i + 1)
		for j in range(n):
			if num_list[i][j] == '1':
				ans[j].add(i + 1)
	for i in ans:
		print(len(i), *i)


import math
import re
import collections
import itertools

def solve():
	n = int(input())
	g = [[] for i in range(n)]
	for i in range(n):
		s = input()
		for j in range(len(s)):
			if s[j] == '1':
				g[j].append(i)
	for j in range(n):
		print(len(g[j]) + 1, end=' ')
		for c in g[j]:
			print(c + 1, end=' ')
		print(j + 1)

def main():
	t = int(input())
	for i in range(t):
		solve()
main()


test = int(input())
from collections import defaultdict
while test:
	n = int(input())
	a = []
	ans = []
	ans.append([])
	for i in range(n):
		a.append(input())
		ans.append([])
	for i in range(1, n + 1):
		ans[i].append(i)
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if a[i - 1][j - 1] == '1':
				ans[j].append(i)
	for i in range(1, n + 1):
		print(len(ans[i]), end=' ')
		for j in ans[i]:
			print(j, end=' ')
		print()
	test -= 1


import sys
FILE = False
if FILE:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def get_int():
	return int(sys.stdin.readline())

def get_string():
	return sys.stdin.readline().strip()
test_cases = get_int()
for test in range(test_cases):
	n = get_int()
	matrix = [''] * (n + 1)
	sets = [set() for i in range(n + 1)]
	for i in range(1, n + 1):
		input = get_string()
		matrix[i] = ' ' + input
		for j in range(1, n + 1):
			if matrix[i][j] == '0' and i != j:
				continue
			sets[j].add(i)
	for i in range(1, n + 1):
		print(len(sets[i]), *sets[i])


import sys
T = int(sys.stdin.readline().strip())
for t in range(0, T):
	n = int(sys.stdin.readline().strip())
	A = [[] for i in range(0, n)]
	for i in range(0, n):
		b = sys.stdin.readline().strip()
		A[i].append(i + 1)
		for j in range(0, n):
			if b[j] == '1':
				A[j].append(i + 1)
	for i in range(0, n):
		print(len(A[i]), *A[i])


t = int(input())
for i in range(t):
	n = int(input())
	sol = [[] for i in range(n)]
	for i in range(n):
		line = input()
		for (j, c) in enumerate(line):
			if c == '1':
				sol[j].append(i + 1)
	for (i, s) in enumerate(sol):
		print(len(s) + 1, *s, i + 1)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	ju = [sys.stdin.readline().strip() for _ in range(n)]
	s = [set() for _ in range(n + 1)]
	for i in range(1, 1 + n):
		for j in range(1, n + 1):
			if ju[i - 1][j - 1] == '0' and i != j:
				continue
			s[j].add(i)
	for i in range(1, 1 + n):
		print(len(s[i]), end=' ')
		for j in s[i]:
			print(j, end=' ')
		print()


def f(u):
	a[u] = {u + 1}
	for v in r:
		if '0' < b[v][u]:
			if a[v] == 0:
				f(v)
			a[u] |= a[v]
I = input
for _ in [0] * int(I()):
	r = range((n := int(I())))
	a = [0] * n
	b = [I() for _ in [0] * n]
	for u in r:
		if a[u] == 0:
			f(u)
	for x in a:
		print(len(x), *x)


for _ in range(int(input())):
	a = int(input())
	tr = list()
	for i in range(a):
		g = input()
		tr.append(g)
	li = list()
	for i in range(a):
		li.append({i + 1})
	for i in range(a):
		for j in range(len(tr[i])):
			if tr[i][j] == '1':
				li[j] = li[j].union(li[i])
	for i in range(len(li)):
		print(len(li[i]), end=' ')
		print(' '.join((str(e) for e in li[i])))


def main(x, n):
	res = [2 ** i for i in range(n)]
	for i in range(n):
		for j in range(n):
			if x[i][j] == '1':
				res[j] = res[i] | res[j]
	for r in res:
		r = '{0:b}'.format(r)[::-1]
		print(r.count('1'), end=' ')
		for i in range(len(r)):
			if r[i] == '1':
				print(i + 1, end=' ')
		print()
t = int(input())
for i in range(t):
	n = int(input())
	m = []
	for j in range(n):
		m.append(input())
	main(m, n)


for _ in range(int(input())):
	n = int(input())
	children = [set() for _ in range(n)]
	for i in range(n):
		line = input()
		for j in range(n):
			if line[j] == '1':
				children[i].add(j)
	sets = [set() for _ in range(n)]
	for i in range(n):
		queue = {i}
		while queue:
			cur = queue.pop()
			sets[cur].add(i + 1)
			queue.update(children[cur])
	for s in sets:
		print(len(s), *s)


I = input
for _ in [0] * int(I()):
	r = range(int(I()))
	a = [[i + 1] for i in r]
	for i in r:
		j = 0
		for x in I():
			a[j] += ([], [i + 1])[x > '0']
			j += 1
	for x in a:
		print(len(x), *x)


t = int(input())
for i in range(t):
	n = int(input())
	a = []
	for i in range(n):
		arr = input()
		a.append(arr)
	dic = {}
	for i in range(n):
		for j in range(n):
			if a[i][j] == '1':
				if j not in dic:
					dic[j] = []
				dic[j].append(i + 1)
	ans = []
	for i in range(n):
		ans.append([i + 1])
	for i in dic:
		for j in dic[i]:
			ans[i].append(j)
	for i in range(n):
		print(len(ans[i]), end=' ')
		for j in range(len(ans[i])):
			print(ans[i][j], end=' ')
		print()


for _ in range(int(input())):
	n = int(input())
	g = [set() for i in range(n)]
	ans = [{i + 1} for i in range(n)]
	d = [0] * n
	for i in range(n):
		s = input().strip()
		for j in range(n):
			if s[j] == '1':
				g[i].add(j)
				d[j] += 1
	l = [i for i in range(n) if d[i] == 0]
	while l:
		t = []
		for i in l:
			for j in g[i]:
				ans[j] |= ans[i]
				d[j] -= 1
				if not d[j]:
					t.append(j)
		l = t
	for i in range(n):
		print(len(ans[i]), *ans[i])


def dfs(node):
	global graph, visited, result, cnt
	if visited[node]:
		return
	visited[node] = 1
	for next in graph[node]:
		dfs(next)
		for l in result[next]:
			if l not in result[node]:
				result[node].append(l)
	cnt += 1
	result[node].append(cnt)

def main():
	global graph, visited, result, cnt
	T = int(input())
	while T:
		T -= 1
		n = int(input())
		graph = [[] for _ in range(n)]
		visited = [0 for _ in range(n)]
		result = [[] for _ in range(n)]
		cnt = 0
		for i in range(n):
			t = input()
			for j in range(n):
				if t[j] == '1':
					graph[j].append(i)
		for node in range(n):
			dfs(node)
		for r in result:
			t = ' '.join(map(str, r))
			print(len(r), t)
main()