Let X be the set of all integers between 0 and n-1. Suppose we have a collection S1, S2, ..., Sm of subsets of X. Say an atom A is a subset of X such that for each Si we have either A is a subset of Si or A and Si do not have any common elements.

Your task is to find a collection A1, ..., Ak of atoms such that every item in X is in some Ai and no two Ai, Aj with i ≠ j share a common item. Surely such a collection exists as we could create a single set {x} for each x in X. A more interesting question is to minimize k, the number of atoms.

-----Input-----

The first line contains a single positive integer t ≤ 30 indicating the number of test cases. Each test case begins with two integers n,m where n is the size of X and m is the number of sets Si. Then m lines follow where the i'th such line begins with an integer vi between 1 and n (inclusive) indicating the size of Si. Following this are vi distinct integers between 0 and n-1 that describe the contents of Si.

You are guaranteed that 1 ≤ n ≤ 100 and 1 ≤ m ≤ 
30. Furthermore, each number between 0 and n-1 will appear in at least one set Si.

-----Output-----

For each test case you are to output a single integer indicating the minimum number of atoms that X can be partitioned into to satisfy the constraints.

-----Example-----
Input:
2
5 2
3 0 1 2
3 2 3 4
4 3
2 0 1
2 1 2
2 2 3

Output:
3
4

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Graph algorithms

Graph traversal

Mathematics

Spanning trees

Data structures


Solutions:
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	atomlist = [''] * n
	for k in range(m):
		s = []
		s.extend(input().split()[1:])
		for w in range(n):
			if str(w) in s:
				atomlist[w] += '1'
			else:
				atomlist[w] += '0'
	print(len(set(atomlist)))


def solve():
	(n, m) = (int(x) for x in input().split())
	A = [0] * n
	for i in range(m):
		(_, *S) = [int(x) for x in input().split()]
		for val in S:
			A[val] += 2 ** i
	A.sort()
	k = n
	for i in range(n - 1):
		if A[i] == A[i + 1]:
			k -= 1
	print(k)
for _ in range(int(input())):
	solve()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = [''] * n
	for j in range(m):
		s = []
		s.extend(input().split()[1:])
		for k in range(n):
			if str(k) in s:
				a[k] += '1'
			else:
				a[k] += '0'
	print(len(set(a)))


def solve(n, m, arr):
	vals = [0] * n
	for (i, subarray) in enumerate(arr):
		for val in subarray:
			vals[val] += 2 ** i
	vals = sorted(vals)
	count = n
	for i in range(n - 1):
		if vals[i] == vals[i + 1]:
			count -= 1
	return count
t = int(input())
for _ in range(t):
	(n, m) = (int(x) for x in input().split())
	arrs = []
	for _ in range(m):
		arr = [int(x) for x in input().split()]
		arrs.append(arr[1:])
	print(solve(n, m, arrs))


t = int(input())
for _ in range(t):
	(n, m) = (int(x) for x in input().split())
	arr = [0] * n
	for i in range(m):
		(_, *arr_tmp) = [int(x) for x in input().split()]
		for val in arr_tmp:
			arr[val] += 2 ** i
	arr_sorted = sorted(arr)
	count = n
	prev = arr_sorted[0]
	for val in arr_sorted[1:]:
		if val == prev:
			count -= 1
		prev = val
	print(count)


def find(v, u):
	if v == u[v]:
		return v
	return find(u[v], u)

def union(u, v, uf):
	uf[find(v, uf)] = find(u, uf)

def solve_c(n, m, arr):
	setsmap = [0 for i in range(n)]
	union_find = [i for i in range(n)]
	for (set_index, s_arr) in enumerate(arr):
		for val in s_arr:
			setsmap[val] |= 1 << set_index
	for i in range(n):
		for j in range(i + 1, n):
			if setsmap[i] == setsmap[j]:
				union(i, j, union_find)
	count = 0
	for i in range(n):
		if union_find[i] == i:
			count += 1
	return count
t = int(input())
for _ in range(t):
	(n, m) = (int(x) for x in input().split())
	arrs = []
	for _ in range(m):
		arr = [int(x) for x in input().split()]
		arrs.append(arr[1:])
	print(solve_c(n, m, arrs))


import sys

def solve():
	(n, m) = (int(x) for x in input().split())
	A = [0] * n
	for i in range(m):
		(_, *S) = [int(x) for x in input().split()]
		for val in S:
			A[val] += 2 ** i
	A = sorted(A)
	k = n
	for i in range(n - 1):
		if A[i] == A[i + 1]:
			k -= 1
	print(k)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	atom = [''] * n
	for k in range(m):
		s = []
		s.extend(input().split()[1:])
		for h in range(n):
			if str(h) in s:
				atom[h] += '1'
			else:
				atom[h] += '0'
	print(len(set(atom)))


ind = []

def add(i, j):
	while i != ind[i]:
		i = ind[i]
	while j != ind[j]:
		j = ind[j]
	ind[j] = i

def binarySearch(alist, item):
	first = 0
	last = len(alist) - 1
	found = False
	while first <= last and (not found):
		midpoint = (first + last) // 2
		if alist[midpoint] == item:
			found = True
		elif item < alist[midpoint]:
			last = midpoint - 1
		else:
			first = midpoint + 1
	return found
t = int(input().strip())
while t:
	t -= 1
	ind = []
	(n, m) = map(int, input().strip().split())
	for i in range(n):
		ind.append(i)
	st = []
	for i in range(m):
		l = list(map(int, input().strip().split()[1:]))
		l.sort()
		st.append(l)
	for i in range(n):
		for j in range(i + 1, n):
			if ind[j] != j:
				continue
			for k in range(m):
				if binarySearch(st[k], i) != binarySearch(st[k], j):
					break
			else:
				add(i, j)
	l = sum((1 if ind[i] == i else 0 for i in range(n)))
	print(l)