Indian National Olympiad in Informatics 2013
N people live in Sequence Land. Instead of a name, each person is identified by a sequence of integers, called his or her id. Each id is a sequence with no duplicate elements. Two people are said to be each other’s relatives if their ids have at least K elements in common. The extended family of a resident of Sequence Land includes herself or himself, all relatives, relatives of relatives, relatives of relatives of relatives, and so on without any limit.
Given the ids of all residents of Sequence Land, including its President, and the number K, find the number of people in the extended family of the President of Sequence Land.
For example, suppose N = 4 and K = 2. Suppose the President has id (4, 6, 7, 8) and the other three residents have ids (8, 3, 0, 4), (0, 10), and (1, 2, 3, 0, 5, 8). Here, the President is directly related to (8, 3, 0, 4), who in turn is directly related to (1, 2, 3, 0, 5, 8). Thus, the President’s extended family consists of everyone other than (0, 10) and so has size 3.

-----Input format-----
• Line 1: Two space-separated integers, N followed by K.
• Lines 2 to N + 1: Each line describes an id of one of the residents of Sequence Land, beginning with the President on line 2. Each line consists of an integer p, followed by p distinct integers, the id.

-----Output format-----
The output consists of a single integer, the number of people in the extended family of the President.

-----Test Data-----
The testdata is grouped into two subtasks. In both subtasks, 1 ≤ N ≤ 300 and 1 ≤ K ≤ 300. Each number in each id is between 0 and 109 inclusive.
• Subtask 1 [30 points]: The number of elements in each id is between 1 and 10 inclusive.
• Subtask 2 [70 points]: The number of elements in each id is between 1 and 300 inclusive.

-----Example-----
Here is the sample input and output corresponding to the example above.

-----Sample input -----
4 2
4 4 6 7 8
4 8 3 0 4
2 0 10
6 1 2 3 0 5 8

-----Sample output-----
3

Note: Your program should not print anything other than what is specified in the output format. Please remove all diagnostic print statements before making your final submission. A program with extraneous output will be treated as incorrect!

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def check_relative(i, j):
	if is_relative[i]:
		return
	if len(land[i].intersection(land[j])) >= k:
		is_relative[i] = True
		for ii in range(n):
			check_relative(ii, i)
(n, k) = map(int, input().split())
land = []
is_relative = [True] + [False] * (n - 1)
for i in range(n):
	(p, *q) = input().split()
	land.append(set(map(int, q)))
for i in range(n):
	check_relative(i, 0)
print(is_relative.count(True))


import sys
sys.setrecursionlimit(10 ** 9)

def check_relative(i, j):
	if is_relative[i]:
		return
	if len(land[i].intersection(land[j])) >= k:
		is_relative[i] = True
		for ii in range(n):
			check_relative(ii, i)
(n, k) = map(int, input().split())
land = []
is_relative = [False] * n
for i in range(n):
	(p, *q) = input().split()
	land.append(set(map(int, q)))
for i in range(n):
	check_relative(i, 0)
print(is_relative.count(True))


from collections import defaultdict
(n, k) = list(map(int, input().split()))
b = []
drel = defaultdict(list)
ans = 0
for i in range(n):
	a = list(map(int, input().split()))
	b.append(set(a[1:]))
for i in range(n):
	for j in range(n):
		if i != j:
			m = 0
			for l in b[j]:
				if l in b[i]:
					m += 1
				if m >= k:
					drel[i].append(j)
					break
visited = set()

def dfs(node):
	global ans
	visited.add(node)
	for i in drel[node]:
		if i not in visited:
			ans += 1
			dfs(i)
dfs(0)
print(ans + 1)


def dfs(graph, i):
	visited[i] = True
	for j in graph[i]:
		if not visited[j]:
			dfs(graph, j)
(N, K) = map(int, input().split())
arr = []
for i in range(N):
	arr.append(list(map(int, input().split())))
nodes = [[] for _ in range(N)]
for i in range(N - 1):
	for j in range(i + 1, N):
		count = len(set(arr[i]).intersection(set(arr[j])))
		if count >= K:
			nodes[i].append(j)
			nodes[j].append(i)
visited = [False] * N
dfs(nodes, 0)
print(visited.count(True))


from collections import defaultdict

def friend(i, j, k):
	counter = 0
	for num in ids[i]:
		if (j, num) in insieme:
			counter += 1
		if counter == k:
			break
	if counter == k:
		return True
	return False
(n, k) = map(int, input().split())
ids = []
insieme = set()
for i in range(n):
	id = list(map(int, input().split()))
	id = id[1:]
	for el in id:
		insieme.add((i, el))
	ids.append(id)
graph = defaultdict(lambda : [])
for i in range(n - 1):
	for j in range(i + 1, n):
		if friend(i, j, k):
			graph[i].append(j)
			graph[j].append(i)
visited = [0] * n
visited[0] = 1
stack = [0]
counter = 1
while len(stack) > 0:
	u = stack.pop()
	for v in graph[u]:
		if visited[v] == 0:
			visited[v] = 1
			stack.append(v)
			counter += 1
print(counter)


(n, k) = map(int, input().split())
l = [0]
vis = [0] * (n + 1)
for i in range(n):
	s = list(map(int, input().split(' ')))
	l.append(s[1:s[0] + 1])
q = []
q.append(1)
sol = 1
while q != []:
	temp = q[0]
	q.pop(0)
	vis[temp] = 1
	for i in range(1, n + 1):
		if vis[i] == 0:
			l1 = len(l[temp])
			l2 = len(l[i])
			len1 = l1 + l2
			slen1 = len(set(l[temp] + l[i]))
			if len1 - slen1 >= k:
				vis[i] = 1
				sol += 1
				q.append(i)
print(sol)


def find_relatives(list1):
	global graph, relatives, K
	temp = {}
	for j in list1:
		if j not in graph:
			list1.remove(j)
	for i in range(len(list1)):
		temp1 = graph[list1[i]]
		for j in temp1:
			try:
				temp[j] += 1
			except:
				temp[j] = 1
	keys = list(temp.keys())
	rel1 = []
	for j in range(len(keys)):
		if temp[keys[j]] >= K:
			if keys[j] not in relatives:
				rel1.append(keys[j])
	return rel1
from collections import defaultdict
(N, K) = map(int, input().split())
listim = list(map(int, input().split()))
listim = listim[1:]
listcit = []
for i in range(N - 1):
	temp = list(map(int, input().split()))
	temp = temp[1:]
	listcit.append(temp)
graph = defaultdict(list)
for i in range(len(listcit)):
	for x in listcit[i]:
		graph[x].append(i)
relatives = []
relatives = set(relatives)
t1 = find_relatives(listim)
rel = t1
for j in rel:
	relatives.add(j)
length = len(relatives)
count = 0
while length != len(relatives) or count == 0:
	length = len(relatives)
	for i in rel:
		t1 = find_relatives(listcit[i])
		rel = t1
		for j in rel:
			relatives.add(j)
	count += 1
print(len(relatives) + 1)


def is_relative(a, b):
	global K
	if len(a.intersection(b)) >= K:
		return True
	else:
		return False

def getval():
	(waste, *v) = map(int, input().split())
	return set(v)
(N, K) = map(int, input().split())
p = getval()
citizens = []
rel = []
for _ in range(N - 1):
	citizens.append(getval())
for citizen in citizens:
	if is_relative(p, citizen):
		rel.append(citizen)
		citizens.remove(citizen)
for relative in rel:
	for citizen in citizens:
		if is_relative(relative, citizen):
			rel.append(citizen)
			citizens.remove(citizen)
print(len(rel) + 1)


from fractions import Fraction
import numpy as np
import sys, bisect, copyreg, copy, statistics, os
from math import *
from collections import Counter, defaultdict, deque, OrderedDict
from itertools import combinations, permutations, accumulate, groupby
from numpy.linalg import matrix_power as mp
from bisect import bisect_left, bisect_right, bisect, insort, insort_left, insort_right
from statistics import mode
from functools import reduce, cmp_to_key
from io import BytesIO, IOBase
from scipy.spatial import ConvexHull
from heapq import *
from decimal import *
from queue import Queue, PriorityQueue
from re import sub, subn
if sys.version_info[0] < 3:
	from builtins import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def bfs(adj, v):
	visited = [False] * (v + 1)
	q = deque()
	while q:
		pass

def graph(vertex):
	return [[] for i in range(vertex + 1)]

def powermodulo(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def lcm(a, b):
	return a * b // gcd(a, b)

def most_frequent(List):
	return Counter(List).most_common(1)[0][0]

def most_common(List):
	return mode(List)

def chinese_remainder(a, p):
	prod = reduce(op.mul, p, 1)
	x = [prod // pi for pi in p]
	return sum((a[i] * powermodulo(x[i], p[i] - 2, p[i]) * x[i] for i in range(len(a)))) % prod

def createMatrix(rowCount, colCount, dataList):
	mat = []
	for i in range(rowCount):
		rowList = []
		for j in range(colCount):
			if dataList[j] not in mat:
				rowList.append(dataList[j])
		mat.append(rowList)
	return mat

def readTree():
	v = int(inp())
	adj = [set() for i in range(v + 1)]
	for i in range(v - 1):
		(u1, u2) = In()
		adj[u1].add(u2)
		adj[u2].add(u1)
	return (adj, v)

def sieve():
	li = [True] * 1000001
	(li[0], li[1]) = (False, False)
	prime = []
	for i in range(2, len(li), 1):
		if li[i] == True:
			for j in range(i * i, len(li), i):
				li[j] = False
	for i in range(1000001):
		if li[i] == True:
			prime.append(i)
	return prime

def setBit(n):
	count = 0
	while n != 0:
		n = n & n - 1
		count += 1
	return count

def digitsSum(n):
	if n == 0:
		return 0
	r = 0
	while n > 0:
		r += n % 10
		n //= 10
	return r

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, list(range(n, n - r, -1)), 1)
	denom = reduce(op.mul, list(range(1, r + 1)), 1)
	return numer // denom

def factors(n):
	return list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return len(set(factors))

def prefixSum(arr):
	for i in range(1, len(arr)):
		arr[i] = arr[i] + arr[i - 1]
	return arr

def binomial_coefficient(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0

def powerOfK(k, max):
	if k == 1:
		return [1]
	if k == -1:
		return [-1, 1]
	result = []
	n = 1
	while n <= max:
		result.append(n)
		n *= k
	return result

def kadane(a, size):
	max_so_far = 0
	max_ending_here = 0
	for i in range(0, size):
		max_ending_here = max_ending_here + a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
		if max_ending_here < 0:
			max_ending_here = 0
	return max_so_far

def divisors(n):
	result = []
	for i in range(1, ceil(sqrt(n)) + 1):
		if n % i == 0:
			if n / i == i:
				result.append(i)
			else:
				result.append(i)
				result.append(n / i)
	return result

def sumtilln(n):
	return n * (n + 1) // 2

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, ceil(sqrt(n)) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def isPowerOf2(n):
	while n % 2 == 0:
		n //= 2
	return True if n == 1 else False

def power2(n):
	k = 0
	while n % 2 == 0:
		k += 1
		n //= 2
	return k

def sqsum(n):
	return n * (n + 1) * (2 * n + 1) // 6

def cusum(n):
	return sumn(n) ** 2

def pa(a):
	for i in range(len(a)):
		print(a[i], end=' ')
	print()

def pm(a, rown, coln):
	for i in range(rown):
		for j in range(coln):
			print(a[i][j], end=' ')
		print()

def pmasstring(a, rown, coln):
	for i in range(rown):
		for j in range(coln):
			print(a[i][j], end='')
		print()

def isPerfectSquare(n):
	return pow(floor(sqrt(n)), 2) == n

def nC2(n, m):
	return n * (n - 1) // 2 % m

def modInverse(n, p):
	return powermodulo(n, p - 2, p)

def ncrmodp(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * powermodulo(den, p - 2, p) % p

def reverse(string):
	return ''.join(reversed(string))

def listtostr(s):
	return ' '.join([str(elem) for elem in s])

def binarySearch(arr, l, r, x):
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	return -1

def isarrayodd(a):
	r = True
	for i in range(len(a)):
		if a[i] % 2 == 0:
			r = False
			break
	return r

def isPalindrome(s):
	return s == s[::-1]

def gt(x, h, c, t):
	return (x * h + (x - 1) * c) / (2 * x - 1)

def CountFrequency(my_list):
	freq = {}
	for item in my_list:
		freq[item] = freq[item] + 1 if item in freq else 1
	return freq

def CountFrequencyasPair(my_list1, my_list2, freq):
	for item in my_list1:
		freq[item][0] = freq[item][0] + 1 if item in freq else 1
	for item in my_list2:
		freq[item][1] = freq[item][1] + 1 if item in freq else 1
	return freq

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			(count, left) = (mid + 1, mid + 1)
		else:
			right = mid - 1
	return count

def primes(n):
	(sieve, l) = ([True] * (n + 1), [])
	for p in range(2, n + 1):
		if sieve[p]:
			l.append(p)
			for i in range(p, n + 1, p):
				sieve[i] = False
	return l

def Next_Greater_Element_for_all_in_array(arr):
	(s, n, reta, retb) = (list(), len(arr), [], [])
	arr1 = [list([0, i]) for i in range(n)]
	for i in range(n - 1, -1, -1):
		while len(s) > 0 and s[-1][0] <= arr[i]:
			s.pop()
		if len(s) == 0:
			arr1[i][0] = -1
		else:
			arr1[i][0] = s[-1]
		s.append(list([arr[i], i]))
	for i in range(n):
		reta.append(list([arr[i], i]))
		retb.append(arr1[i][0])
	return (reta, retb)

def polygonArea(X, Y, n):
	area = 0.0
	j = n - 1
	for i in range(n):
		area += (X[j] + X[i]) * (Y[j] - Y[i])
		j = i
	return abs(area / 2.0)

def merge(a, b):
	ans = defaultdict(int)
	for i in a:
		ans[i] += a[i]
	for i in b:
		ans[i] += b[i]
	return ans

class LRUCache:

	def __init__(self, capacity: int):
		self.cache = OrderedDict()
		self.capacity = capacity

	def get(self, key: int) -> int:
		if key not in self.cache:
			return -1
		else:
			self.cache.move_to_end(key)
			return self.cache[key]

	def put(self, key: int, value: int) -> None:
		self.cache[key] = value
		self.cache.move_to_end(key)
		if len(self.cache) > self.capacity:
			self.cache.popitem(last=False)

class segtree:

	def __init__(self, n):
		self.m = 1
		while self.m < n:
			self.m *= 2
		self.data = [0] * (2 * self.m)

	def __setitem__(self, i, x):
		x = +(x != 1)
		i += self.m
		self.data[i] = x
		i >>= 1
		while i:
			self.data[i] = self.data[2 * i] + self.data[2 * i + 1]
			i >>= 1

	def __call__(self, l, r):
		l += self.m
		r += self.m
		s = 0
		while l < r:
			if l & 1:
				s += self.data[l]
				l += 1
			if r & 1:
				r -= 1
				s += self.data[r]
			l >>= 1
			r >>= 1
		return s

class FenwickTree:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def update(self, x, d):
		while x <= self.n:
			self.bit[x] += d
			x += x & -x

	def query(self, x):
		res = 0
		while x > 0:
			res += self.bit[x]
			x -= x & -x
		return res

	def range_query(self, l, r):
		return self.query(r) - self.query(l - 1)
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')

def inp():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(str(var))

def I():
	return inp()

def II():
	return int(inp())

def FI():
	return float(inp())

def SI():
	return list(str(inp()))

def MI():
	return map(int, inp().split())

def LI():
	return list(MI())

def SLI():
	return sorted(LI())

def MF():
	return map(float, inp().split())

def LF():
	return list(MF())

def SLF():
	return sorted(LF())
MOD = 998244353
mod = 10 ** 9 + 7

def __starting_point():
	(n, k) = MI()
	x = []
	for ii in range(n):
		x.append(set(LI()[1:]))
	v = {}
	v[0] = True
	q = [x[0]]
	for ele in q:
		for j in range(n):
			if not v.get(j, False):
				if len(ele.intersection(x[j])) >= k:
					q.append(x[j])
					v[j] = True
	print(len(q))
__starting_point()


(n, k) = map(int, input().split())
ids = []
pr = list(map(int, input().split()))
pr.pop(0)
relatives = []

def common_member(a, b):
	a_set = set(a)
	b_set = set(b)
	return len(a_set.intersection(b_set))
for _ in range(n - 1):
	ids.append(list(map(int, input().split())))
for i in ids:
	i.pop(0)
for i in ids:
	if common_member(pr, i) >= k:
		relatives.append(i)
		ids.remove(i)
y = 1
while y >= 0:
	y = 0
	for x in relatives:
		for i in ids:
			if common_member(x, i) >= k:
				relatives.append(i)
				ids.remove(i)
				y += 1
	if y == 0:
		y = -1
print(len(relatives) + 1)


n1 = input()
(n, k) = map(int, n1.split())
main_lot = []
rel_mat = []
for i in range(n):
	x1 = []
	for j in range(n):
		x1.append(0)
	rel_mat.append(x1)
for i in range(n):
	rel_mat[i][i] = 1
for gen in range(n):
	length1 = list(map(int, input().split()))
	length1 = length1[1:]
	for lits in range(len(main_lot)):
		independentcunt = 0
		for everyele in range(len(length1)):
			if length1[everyele] in main_lot[lits]:
				independentcunt += 1
		if independentcunt >= k:
			rel_mat[gen][lits] = rel_mat[lits][gen] = 1
			pass
	main_lot.append(length1)
	pass
fami_ly = []
unfam_ily = []
i1te = 0
while i1te < 5:
	new_ele_rel = []
	for ele in rel_mat:
		temp1 = []
		for el1 in ele:
			temp1.append(el1)
		new_ele_rel.append(temp1)
	i1te += 1
	for lists1 in range(len(rel_mat)):
		unfam_ily = [i2 for i2 in range(n)]
		fami_ly = [i1 for i1 in range(len(rel_mat[lists1])) if rel_mat[lists1][i1] == 1]
		fami_ly.remove(lists1)
		unfam_ily.remove(lists1)
		for tem1 in fami_ly:
			unfam_ily.remove(tem1)
		unfami_ly = [i2 for i2 in range(len(rel_mat[lists1])) if rel_mat[lists1][i2] == 0]
		for iter1 in fami_ly:
			for iter2 in unfam_ily:
				if new_ele_rel[iter1][iter2] == 1:
					new_ele_rel[iter2][lists1] = 1
					new_ele_rel[lists1][iter2] = 1
					pass
				pass
		fami_ly = []
		unfam_ily = []
count = sum(new_ele_rel[0])
print(count)


from collections import defaultdict

def dfs(graph, i):
	visited[i] = True
	for j in graph[i]:
		if not visited[j]:
			dfs(graph, j)
(n, k) = map(int, input().split())
arr = []
for i in range(n):
	arr.append(list(map(int, input().split()))[1:])
graph = defaultdict(list)
for i in range(n):
	for j in range(i + 1, n):
		c = len(set(arr[i]).intersection(set(arr[j])))
		if c >= k:
			graph[i].append(j)
			graph[j].append(i)
visited = [False] * n
dfs(graph, 0)
print(visited.count(True))


(n, k) = map(int, input().split())
x = []
for _ in range(n):
	x.append(set([int(w) for w in input().split()][1:]))
vis = {}
vis[0] = True
q = [x[0]]
for ele in q:
	for j in range(n):
		if not vis.get(j, False):
			if len(ele.intersection(x[j])) >= k:
				q.append(x[j])
				vis[j] = True
print(len(q))


import sys

def dfs(adj, n):
	vis[n] = True
	for i in adj[n]:
		if vis[i] == False:
			dfs(adj, i)
sys.setrecursionlimit(10 ** 9)
(n, k) = map(int, input().split())
a = []
for i in range(n):
	t = list(map(int, input().split()))
	a.append(t[1:])
adj = []
global vis
vis = [False] * n
for i in range(n):
	adj.append([])
for i in range(n):
	for j in range(i + 1, n):
		c = len(set(a[i]).intersection(set(a[j])))
		if c >= k:
			adj[i].append(j)
			adj[j].append(i)
dfs(adj, 0)
c = 0
for i in range(0, n):
	if vis[i] == True:
		c += 1
print(c)


(n, k2) = map(int, input().split())
l = []
for i in range(n):
	t = input().split()
	t = [int(x) for x in t]
	l.append([])
	l[i] = t[1:]
total = 1
ans = set(l[0])
notPres = []
for i in l[1:]:
	count = 0
	temp = []
	for j in i:
		if j in ans:
			count += 1
	if count >= k2:
		total += 1
		for j in i:
			ans.add(j)
		index = []
		indC = 0
		for k in notPres:
			c = 0
			for l in k:
				if l in ans:
					c += 1
			if c >= k2:
				total += 1
				for l in k:
					ans.add(l)
				index.append(indC)
			indC += 1
		for i in index:
			notPres[i] = []
	else:
		notPres.append(i)
for i in notPres:
	c = 0
	for l in i:
		if l in ans:
			c += 1
			if c >= k2:
				total += 1
				for l in k:
					ans.add(l)
print(total)