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!

Difficulty: interview

Starter code:

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))

def check_relative(i,j):
    if is_relative[i] or i==j: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(q))

for i in range(n):
    check_relative(i,0)
        
print(is_relative.count(True))

def check_relative(i,j):
    if is_relative[i]:return
    if j in direct_relatives[i] or i in direct_relatives[j]:
        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(q))

direct_relatives={k:set() for k in range(n)}
for i in range(n):
    for j in range(n):
        if len(land[i].intersection(land[j]))>=k:
            direct_relatives[i].add(j)

for i in range(n):
    check_relative(i,0)
        
print(is_relative.count(True))

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(q))

for i in range(n):
    check_relative(i,0)
        
print(is_relative.count(True))

def check_relative(i,j):
    if is_relative[i]:return
    if len(land[i].intersection(land[j]))>=2:
        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(q))

for i in range(n):
    check_relative(i,0)
        
print(is_relative.count(True))

# cook your dish here
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)

# cook your dish here
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)



# cook your dish here
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)


# cook your dish here
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(a[1:])
for i in range(n):
    for j in range(n):
        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))






# cook your dish here
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)        

# cook your dish here
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)

    

# cook your dish here
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=[]
t1 = find_relatives(listim)
rel = t1
for j in rel:
    relatives.append(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.append(j)
    count +=1
print(len(relatives)+1)

    

# cook your dish here
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=[]
t1 = find_relatives(listim)
rel = t1
for j in rel:
    relatives.append(j)
while len(rel)!=0:
    for i in rel:
        t1 = find_relatives(listcit[i])
        rel = t1
        for j in rel:
            relatives.append(j)
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)
#print(rel)
for relative in rel:
    for citizen in citizens:
        if is_relative(relative,citizen):
            rel.append(citizen)
            #print(rel)
            citizens.remove(citizen)
print(len(rel)+1)


# import all important libraries and inbuilt functions

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

# end of library import

# map system version faults
if sys.version_info[0] < 3:
    from builtins import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

# template of many functions used in competitive programming can add more later 
# based on need we will use this commonly.

# bfs in a graph
def bfs(adj,v): # a schema of bfs
    visited=[False]*(v+1);q=deque()
    while q:pass

# definition of vertex of a graph
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)

# most common list in a array of lists
def most_frequent(List):return Counter(List).most_common(1)[0][0]

# element with highest frequency
def most_common(List):return(mode(List))

#In number theory, the Chinese remainder theorem states that 
#if one knows the remainders of the Euclidean division of an integer n by 
#several integers, then one can determine uniquely the remainder of the 
#division of n by the product of these integers, under the condition 
#that the divisors are pairwise coprime.
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

# make a matrix
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

# input for a binary tree
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
    
# sieve of prime numbers    
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

#count setbits of a number.
def setBit(n):
    count=0
    while n!=0:n=n&(n-1);count+=1
    return count

# sum of digits of a number
def digitsSum(n):
    if n == 0:return 0
    r = 0
    while n > 0:r += n % 10;n //= 10
    return r

# ncr efficiently
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  # or / in Python 2

#factors of a number
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))))

#prime fators of a number
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

# maximum subarray sum use kadane's algorithm
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
 
#defining a LRU Cache
# where we can set values and get values based on our requirement
class LRUCache: 
	# initialising capacity 
	def __init__(self, capacity: int): 
		self.cache = OrderedDict() 
		self.capacity = capacity 

	# we return the value of the key 
	# that is queried in O(1) and return -1 if we 
	# don't find the key in out dict / cache. 
	# And also move the key to the end 
	# to show that it was recently used. 
	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] 

	# first, we add / update the key by conventional methods. 
	# And also move the key to the end to show that it was recently used. 
	# But here we will also check whether the length of our 
	# ordered dictionary has exceeded our capacity, 
	# If so we remove the first key (least recently used) 
	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)        
# can add more template functions here
    
# end of template functions

# To enable the file I/O i the below 2 lines are uncommented.
# read from in.txt if uncommented
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
# will print on Console if file I/O is not activated
#if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')

# inputs template
#for fast input we areusing sys.stdin
def inp(): return sys.stdin.readline().strip()

#for fast output, always take string
def out(var): sys.stdout.write(str(var))  

# cusom base input needed for the program
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()))

# end of inputs template

# common modulo values used in competitive programming
MOD = 998244353
mod = 10**9+7

# any particular user-defined functions for the code.
# can be written here.  
 
# end of any user-defined functions

# main functions for execution of the program.
def __starting_point():  
    # execute your program from here.
    # start your main code from here
        
    # Write your code here
    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))
                                    
    # end of main code
    # end of program

# This program is written by :
#   Shubham Gupta
#   B.Tech (2019-2023)
#   Computer Science and Engineering,
#   Department of EECS
#   Contact No:8431624358
#   Indian Institute of Technology(IIT),Bhilai
#   Sejbahar,
#   Datrenga,
#   Raipur,
#   Chhattisgarh
#   492015

#   THANK YOU FOR 
#YOUR KIND PATIENCE FOR READING THE PROGRAM.    
__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()
# k = int(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):
    # print(i)
    rel_mat[i][i] = 1
# print(rel_mat)
for gen in range(n):
    length1 = list(map(int, input().split()))
    length1 = length1[1:]
    # print(length1)
    for lits in range(len(main_lot)):
        independentcunt = 0
        # main_lot[lits]
        for everyele in range(len(length1)):
            # length1[everyele]
            if length1[everyele] in main_lot[lits]:
                independentcunt += 1
        # print(independentcunt)
        if independentcunt>=k:
            rel_mat[gen][lits] = rel_mat[lits][gen] = 1
            pass
    main_lot.append(length1)
    pass


# print(n)
# print(k)

# print(main_lot)
# print(rel_mat)
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:
                    # print("did reach")

                    new_ele_rel[iter2][lists1] = 1
                    new_ele_rel[lists1][iter2] = 1
                    # print(new_ele_rel[lists1][iter1])
                    # print(iter1,lists1)
                    # print(new_ele_rel)

                    pass 
                pass 
        #     pass
        # print(fami_ly)
        # print(unfam_ily)
        fami_ly = []
        unfam_ily = []

        # print(rel_mat)



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:]))

# using bfs

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

#ct = dfs(0,x[0],0,vis)

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:]
# print(l)

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(notPres)
print(total)


(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:]
# print(l)

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=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)
                notPres[index]=[]
            index+=1
    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(notPres)
print(total)