Problem:
 Score : 400 points    Problem Statement On a planet far, far away, M languages are spoken. They are conveniently numbered 1 through M .  For CODE FESTIVAL 20XX held on this planet, N participants gathered from all over the planet.  The i -th (1≦i≦N) participant can speak K_i languages numbered L_{i,1}, L_{i,2}, ..., L_{i,{}K_i} .  Two participants A and B can communicate with each other if and only if one of the following conditions is satisfied:   There exists a language that both A and B can speak.  There exists a participant X that both A and B can communicate with.   Determine whether all N participants can communicate with all other participants.      Constraints  2≦N≦10^5  1≦M≦10^5  1≦K_i≦M  ( The sum of all K_i)≦10^5  1≦L_{i,j}≦M  L_{i,1}, L_{i,2}, ..., L_{i,{}K_i} are pairwise distinct.       Partial Score  200 points will be awarded for passing the test set satisfying the following: N≦1000 , M≦1000 and ( The sum of all K_i)≦1000 .  Additional 200 points will be awarded for passing the test set without additional constraints.         Input The input is given from Standard Input in the following format:  N  M  K_1  L_{1,1}  L_{1,2}  ...  L_{1,{}K_1}  K_2  L_{2,1}  L_{2,2}  ...  L_{2,{}K_2}  :  K_N  L_{N,1}  L_{N,2}  ...  L_{N,{}K_N}       Output If all N participants can communicate with all other participants, print YES . Otherwise, print NO .        Sample Input 1 4 6
3 1 2 3
2 4 2
2 4 6
1 6      Sample Output 1 YES  Any two participants can communicate with each other, as follows:   Participants 1 and 2 : both can speak language 2 .  Participants 2 and 3 : both can speak language 4 .  Participants 1 and 3 : both can communicate with participant 2 .  Participants 3 and 4 : both can speak language 6 .  Participants 2 and 4 : both can communicate with participant 3 .  Participants 1 and 4 : both can communicate with participant 2 .   Note that there can be languages spoken by no participant.       Sample Input 2 4 4
2 1 2
2 1 2
1 3
2 4 3      Sample Output 2 NO  For example, participants 1 and 3 cannot communicate with each other.

Solution (Python):
import sys
import heapq
import bisect
import itertools

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def LI_(): return([int(x)-1 for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                prime[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    N,M = LI()
    ll = [[] for _ in range(N)]
    dic = {}
    for i in range(N):
        KL = LI()
        ll[i] = [j-1 for j in KL[1:]]
        for l in KL[1:]:
            dic[l-1] = dic.get(l-1,[])
            dic[l-1].append(i)

    flagk = [True] * N
    flagl = {}
    for l in dic:
        flagl[l] = True

    que = [0]
    while que:
        k = que.pop()
        if flagk[k]:
            flagk[k] = False
            for l in ll[k]:
                if flagl[l]:
                    flagl[l] = False
                    for nxt in dic[l]:
                        if flagk[nxt]:
                            que.append(nxt)
    for x in flagk:
        if x:
            return("NO")
    return("YES")



if __name__ == "__main__":
    print(main())

Solution (Python):

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size + 1)]
        self.rank = [0] * (size + 1)

    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    N, M = map(int, input().split())
    A = [(map(int, input().split())) for _ in range(N)]
    uf, spoken = UnionFind(M), set()
    for _, *langs in A:
        spoken.update(langs)
        primary = langs[0]
        for l in langs[1:]:
            uf.unite(primary, l)
    cur = uf.find(spoken.pop())
    flg = all(uf.find(lang) == cur for lang in spoken)
    print("YES" if flg else "NO")


if __name__ == "__main__":
    main()

Solution (Python):

class UnionFind:  
    def __init__(self, size):  
        self.parent = [i for i in range(size + 1)]
        self.rank = [0] * (size + 1)

    def find(self, x):  
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):  
        x, y = self.find(x), self.find(y)
        if x == y:  
            return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    
    N, M = map(int, input().split())
    A = [(map(int, input().split())) for _ in range(N)]
    uf, spoken = UnionFind(M), set()
    for _, *langs in A:
        spoken.update(langs)
        primary = langs[0]  
        for l in langs[1:]:
            uf.unite(primary, l)
    cur = uf.find(spoken.pop())  
    flg = all(uf.find(lang) == cur for lang in spoken)
    print("YES" if flg else "NO")


if __name__ == "__main__":
    main()

Solution (Python):

class UnionFind:  
    def __init__(self, size):  
        self.parent = [i for i in range(size + 1)]
        self.rank = [0] * (size + 1)

    def find(self, x):  
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):  
        x, y = self.find(x), self.find(y)
        if x == y:  
            return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    
    N, M = map(int, input().split())
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    uf, spoken = UnionFind(M), set()
    for _, *langs in A:
        spoken.update(langs)
        primary = langs[0]
        for l in langs[1:]:
            uf.unite(primary, l)
    cur = uf.find(spoken.pop())  
    flg = all(uf.find(lang) == cur for lang in spoken)
    print("YES" if flg else "NO")


if __name__ == "__main__":
    main()

Solution (Python):

class UnionFind:  
    def __init__(self, size):  
        self.parent = [i for i in range(size + 1)]
        self.rank = [0] * (size + 1)

    def find(self, x):  
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def is_same(self, x, y):  
        return self.find(x) == self.find(y)

    def unite(self, x, y):  
        x, y = self.find(x), self.find(y)
        if x == y:  
            return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    N, M = map(int, input().split())
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    uf, spoken = UnionFind(M), set()
    for _, *langs in A:
        spoken.update(langs)
        primary = langs[0]
        for l in langs[1:]:
            uf.unite(primary, l)
    cur = uf.find(spoken.pop())
    flg = all(uf.find(lang) == cur for lang in spoken)
    print("YES" if flg else "NO")


if __name__ == "__main__":
    main()

Solution (Python):


def dfs() -> None:
    stack = [(1, 1)]
    seen_m[1] = 1
    while stack:
        v, flg = stack.pop()
        if flg:
            for u in men[v]:
                if not seen_l[u]:
                    stack.append((u, 0))
                    seen_l[u] = 1
        else:
            for u in langs[v]:
                if not seen_m[u]:
                    stack.append((u, 1))
                    seen_m[u] = 1


def main():
    global men, langs, seen_m, seen_l
    N, M = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    men, langs = [[] for _ in range(N + 1)], [[] for _ in range(M + 1)]
    for person, lang in enumerate(A, 1):  
        for l in lang[1:]:
            men[person].append(l), langs[l].append(person)
    seen_m, seen_l = [0] * (N + 1), [0] * (M + 1)
    dfs()
    flg = all(i for i in seen_m[1:])
    print("YES" if flg else "NO")


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

def same_tree(node_a, node_b):
    if node_a.root() == node_b.root():
        return True

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

def main():
    N, M = map(int, input().split())
    kl = [list(map(int, input().split())) for i in range(N)]

    nodes = [Node() for i in range(M)]
    peaple = [Node() for i in range(N)]

    for i in range(N):
        l = kl[i][1:]
        peaple[i].is_root = False
        peaple[i].parent = nodes[l[0]-1]
        for j in range(1, len(l)):
            unite(nodes[l[j]-1], nodes[l[j-1]-1])
    
    ok = True
    for i in range(1, N):
        if not same_tree(peaple[0], peaple[i]):
            ok = False
    
    if ok:
        print("YES")
    else:
        print("NO")

if __name__ == "__main__":
    main()

Solution (Python):
n,m=map(int,input().split())
par=[-1]*(n+m)

def find(x):
  if par[x]<0:
    return x
  else:
    par[x]=find(par[x])
    return par[x]

def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return False
  else:
    if par[x]>par[y]:
      x,y=y,x
    par[x]+=par[y]
    par[y]=x
    return True

def same(x,y):
  return find(x)==find(y)

def size(x):
  return -par[find(x)]

for i in range(n):
  KL=[int(i) for i in input().split()]
  for j in range(1,len(KL)):
    unite(i,n+KL[j]-1)
chk=True
for i in range(1,n):
  if not same(0,i):
    chk=False
print("YES" if chk==True else "NO")

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size

    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)

    def same(self, x, y):
        return (self.find(x) == self.find(y))

    def size(self, x):
        return -self.data[self.find(x)]


N, M = map(int, input().split())
uf = UnionFind(M + 1)
used = set()
for _ in range(N):
    K, *L = map(int, input().split())
    for l in L:
        uf.union(L[0], l)
    used.update(L)

if uf.size(used.pop()) == 1 + len(used):
    print("YES")
else:
    print("NO")

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size

    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)

    def same(self, x, y):
        return (self.find(x) == self.find(y))

    def size(self, x):
        return -self.data[self.find(x)]


N, M = map(int, input().split())
uf = UnionFind(N + M + 1)
used = set()
for i in range(1, N + 1):
    K, *L = map(int, input().split())
    for l in L:
        uf.union(i, l + N)
        used.add(l)

if uf.size(1) - len(used) == N:
    print("YES")
else:
    print("NO")

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size

    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)

    def same(self, x, y):
        return (self.find(x) == self.find(y))

    def size(self, x):
        return -self.data[self.find(x)]


N, M = map(int, input().split())
uf = UnionFind(N + M + 1)
used = [False] * (M + 1)
for i in range(1, N + 1):
    K, *L = map(int, input().split())
    for l in L:
        uf.union(i, l + N)
        used[l] = True

if uf.size(1) - sum(used) == N:
    print("YES")
else:
    print("NO")

Solution (Python):
class UnionFind:
	def __init__(self, size):
		self.data = [-1] * size
	def find(self, x):
		if self.data[x] < 0:
			return x
		else:
			self.data[x] = self.find(self.data[x])
			return self.data[x]
	def union(self, x, y):
		x, y = self.find(x), self.find(y)
		if x != y:
			if self.data[y] < self.data[x]:
				x, y = y, x
			self.data[x] += self.data[y]
			self.data[y] = x
		return (x != y)
	def same(self, x, y):
		return (self.find(x) == self.find(y))

N, M = map(int, input().split())
uf = UnionFind(N + M + 1)
for i in range(1, N + 1):
	K, *L = map(int, input().split())
	for l in L:
		uf.union(i, l + N)

if all(uf.same(i, N) for i in range(1, N)):
	print("YES")
else:
	print("NO")

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.data = [-1 for _ in range(size)]
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]

N, M = map(int, input().split())
uf = UnionFind(N + M + 1)
for i in range(1, N + 1):
    K, *L = map(int, input().split())
    for l in L:
        uf.union(i, l + N)

if all(uf.same(i, N) for i in range(1, N)):
    print("YES")
else:
    print("NO")

Solution (Python):
from collections import deque

N,M = map(int, input().split())

es_lang = [[] for _ in range(M+1)] 
es_p = [[] for _ in range(N+1)] 
for i in range(N):
    KL = list(map(int, input().split()))
    es_p[i+1].extend(KL[1:])
    for j in KL[1:]:
        es_lang[j].append(i+1)

checked_lang = [False] * (M+1)
checked_p = [False] * (N+1)


stack_p = [1]
checked_p[1] = True
while len(stack_p) > 0:
    new_stack_p = [] 
    for p in stack_p:
        checked_p[p] = True
        stack_lang = []
        for lang in es_p[p]: 
            if checked_lang[lang] == False: 
                stack_lang.append(lang)
                checked_lang[lang] = True

        
        for lang in stack_lang:
            for pp in es_lang[lang]: 
                if checked_p[pp] == False: 
                    new_stack_p.append(pp)
                    checked_p[pp] = True

    if all(checked_p[1:]):
        print("YES")
        exit()
    if len(new_stack_p) > 0:
        stack_p = new_stack_p
    else:
        break



print("NO")

Solution (Python):
N, M = map(int, input().split())
K = [0] * N
L = [[] for _ in range(N + M)]
R = [i for i in range(N + M)]
def find(i):
  if R[i] == i:
    return i
  r = find(R[i])
  R[i] = r
  return r
def union(i, j):
  ri = find(i)
  rj = find(j)
  if ri > rj:
    R[ri] = rj
  else:
    R[rj] = ri
for i in range(N):
  _L = [int(x) + N - 1  for x in input().split()]
  for l in _L[1:]:
    union(i, l)
for i in range(N):
  find(i)
  if R[i]:
    print('NO')
    break
else:
  print('YES')

Solution (Python):
N, M = map(int, input().split())
L = []
for i in range(N):
  Ls = list(map(int, input().split()))
  Ls.pop(0)
  Ls = [l-1 for l in Ls]
  L.append(Ls)

UF = list(range(N+M))
def par(m):
  s = []
  r = UF[m]
  while r != m:
    s.append(m)
    m = r
    r = UF[m]
  for i in s:
    UF[i] = r
  return r
def unite(m, n):
  i = par(m)
  j = par(n)
  UF[j] = i
for i in range(N):
  Ls = L[i]
  for l in Ls:
    unite(i, N+l)
    unite(N+l, i)




ok = True
for i in range(1, N):
  if par(i) != par(i-1):
    ok = False
    break
if ok:
  print("YES")
else:
  print("NO")

Solution (Python):
N, M = map(int, input().split())
L = {}
for i in range(N):
    A = list(map(int, input().split()))
    for j, a in enumerate(A):
        if j == 0:
            continue
        if not a-1 in L.keys():
            L[a-1] = [i]
        else:
            L[a-1].append(i)

class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

union = UnionFind(N)

for list_l in L.values():
    for l in list_l:
        union.Unite(l, list_l[0])

ans = "YES"
for i in range(N):
    if not union.isSameGroup(0, i):
        ans = "NO"
print(ans)

Solution (Python):


class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

    
"""
実装例
ABC126E 1or2



UFコードは省略
    
if __name__ == "__main__":
  
    N,M = map(int,input().split())
    uf = UnionFind(N+1)
    for i in range(M):
        X,Y,Z = map(int,input().split())
        if not uf.isSameGroup(X,Y):
            uf.Unite(X,Y)
    ans=0
    for j in uf.root[1:N+1]:
        if j < 0:
            ans+=1
    print(ans)
"""


N,M = map(int,input().split())
edges = []

for i in range(N):
    Linput = list(map(int,input().split()))
    k = Linput[0]
    for j in range(k):
        L = Linput[j+1]+N-1
        edges.append([i,L])
        
uf = UnionFind(N+M)
for edge in edges:
    x,y = edge[0],edge[1]
    if not uf.isSameGroup(x,y):
        uf.Unite(x,y)
        
flag = 0
for i in range(N-1):
    I = i+1
    if not uf.isSameGroup(0,I):
        flag = 1
        break
        
print("YES" if flag == 0 else "NO")

Solution (Python):



import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def union(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

n,m = LI()
par = [i for i in range(n)]
rank = [0]*n
language = [[] for _ in range(m)]
for i in range(n):
    a = LI()
    k = a[0]
    for j in range(1,k+1):
        language[a[j]-1].append(i)
for i in range(m):
    l = len(language[i])
    for j in range(l-1):
        if root(language[i][j]) != root(language[i][j+1]):
                union(language[i][j],language[i][j+1])
for i in range(m)[::-1]:
    l = len(language[i])
    for j in range(l-1):
        if root(language[i][j]) != root(language[i][j+1]):
            union(language[i][j],language[i][j+1])
for i in range(n-1):
    if par[i] != par[i+1]:
        print('NO')
        quit()
print('YES')

Solution (Python):
class UnionFind:
    def __init__(self,n):
        self.ps = [-1]*(n+1)
    def find(self,x):
        if self.ps[x]<0:
            return x
        else:
            self.ps[x]=self.find(self.ps[x])
            return self.ps[x]
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return False
        if self.ps[x]>self.ps[y]:
            x,y = y,x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True
    def same(self,x,y):
        return self.find(x)==self.find(y)
    def size(self,x):
        x = self.find(x)
        return -self.ps[x]

n,m = map(int, input().split())
uf = UnionFind(n+m)
for i in range(1,n+1):
  l = list(map(int, input().split()))
  for j in range(1,1+l[0]):
    uf.unite(i,n+l[j])
for i in range(n+1,n+m+1):
  if uf.size(i) == 1:
    uf.unite(1,i)
print("YES" if uf.size(1) == n+m else "NO")

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

    def same(self,x,y):
        return self.find(x)==self.find(y)


N,M = [int(x) for x in input().split()]
people = [[i+M+1]+[int(x) for x in input().split()]for i in range(N)]

un = UnionFind(N+M+1)
for p in people:
    num=p[0]
    L=p[2:]
    for l in L:
        un.unite(num,l)
for i in range(M+2,M+N+1):
    if(not un.same(M+1,i)):
        print('NO')
        break
else:
    print('YES')

Solution (Python):
class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
n,m=map(int,input().split())
UF=UnionFind(n+m)
s=set()
for i in range(n):
    l=list(map(int,input().split()))
    for j in l[1:]:
        UF.Unite(i,n+j-1)
        s.add(j)
print("YES" if UF.Count(0)-len(s)==n else "NO")

Solution (Python):
from collections import deque
N,M = map(int,input().split())
edge = [[]for i in range(N+M)]
for i in range(N):
    l = list(map(int,input().split()))[1:]
    for j in l:
        edge[i].append(N+j-1)
        edge[N+j-1].append(i)
A = [0]*(N+M)
A[0] = 1
queue = deque([0])
while queue != deque([]):
    p = queue.popleft()
    for i in edge[p]:
        if A[i] == 0:
            A[i] = 1
            queue.append(i)
if sum(A[:N]) == N:
    print("YES")
else:
    print("NO")

Solution (Python):
N,M=map(int,input().split())
L=[list(map(int,input().split())) for i in range(N)]
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
u=UnionFind(M)
used=[0]*M
for x,*l in L:
    used[l[0]-1]=1
    for i in range(x-1):
        used[l[i+1]-1]=1
        u.unite(l[i]-1,l[i+1]-1)
print(['NO','YES'][u.size(L[0][1]-1)==sum(used)])

Solution (Python):
n,m=map(int,input().split())
p_list=[list(map(lambda x:int(x)-1,input().split()))[1:] for _ in [0]*n]

p_check=[False for _ in [0]*n]
l_check=[False for _ in [0]*m]
l_list=[[] for _ in [0]*m]

for k,i in enumerate(p_list):
    for j in i:
        l_list[j].append(k)

for i,j in enumerate(l_list):
    if j!=[]:
        q=[i]
        break

l_check[q[0]]=True

while q:
    qq=q.pop()
    p=l_list[qq]
    for pp in p:
        if p_check[pp]==False:
            p_check[pp]=True
            for l in p_list[pp]:
                if l_check[l]==False:
                    l_check[l]=True
                    q.append(l)

print(["NO","YES"][all(p_check)])

Solution (Python):

N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N]

E = [[] for _ in [0]*(N+M)] 
for i,kl in enumerate(KL):
    for l in kl[1:]:
        E[i].append(N+l-1)
        E[N+l-1].append(i)

def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        qq = []
        for i in q:
            di = d[i]
            for j in E[i]:
                if d[j]!=-1:continue
                d[j] = di+1
                q.append(j)
        q = qq
    return d

d = dist_bfs(N+M,E,0)
ans = d[:N].count(-1)==0
print("YES" if ans else "NO")

Solution (Python):

N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N]

E = [[] for _ in [0]*(N+M)] 
for i,kl in enumerate(KL):
    for l in kl[1:]:
        E[i].append(N+l-1)
        E[N+l-1].append(i)

def connect_bfs(N,E,start):
    connect = {start}
    q = [start]
    while q:
        i = q.pop()
        for j in E[i]:
            if j in connect:continue
            connect.add(j)
            q.append(j)
    return connect

c = connect_bfs(N+M,E,0)
ans = len(c & set(range(N)))==N
print("YES" if ans else "NO")

Solution (Python):
import heapq
N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N]

E = [{} for _ in [0]*(N+M)]
for i,kl in enumerate(KL):
    for l in kl[1:]:
        E[i][N+l-1] = 1
        E[N+l-1][i] = 1

def Dijkstra(N,E,start):
    d = [-1]*N
    q = [(0,start)]
    while q:
        ci,i = heapq.heappop(q)
        if d[i]!= -1:continue
        d[i] = ci
        for j,cj in E[i].items():
            if d[j]!=-1:continue
            heapq.heappush(q,(ci+cj,j))
    return d

d = Dijkstra(N+M,E,0)
ans = d[:N].count(-1)==0
print("YES" if ans else "NO")

Solution (Python):
N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N]

E = [[] for _ in [0]*(N+M)]
for i,kl in enumerate(KL):
    for l in kl[1:]:
        E[i].append(N+l-1)
        E[N+l-1].append(i)

def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        i = q.pop()
        di = d[i]
        for j in E[i]:
            if d[j]!=-1:continue
            d[j] = di+1
            q.append(j)
    return d

d = dist_bfs(N+M,E,0)
ans = d[:N].count(-1)==0
print("YES" if ans else "NO")

Solution (Python):
N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N]

E = [[] for _ in [0]*(N+M)]
for i,kl in enumerate(KL):
    for l in kl[1:]:
        E[i].append(N+l-1)
        E[N+l-1].append(i)

start = 0
d = [-1]*(N+M) 
d[start] = 0
q = [start]
while q:
    i = q.pop()
    for j in E[i]:
        if d[j]!=-1:continue
        d[j] = d[i]+1
        q.append(j)

ans = True
for b in d[:N]:
    ans = ans and (b>=0)
print("YES" if ans else "NO")

Solution (Python):

N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N]

c = [False]*(N+M) 
E = [[] for _ in [0]*(N+M)]
for i,kl in enumerate(KL):
    for l in kl[1:]:
        E[i].append(N+l-1)
        E[N+l-1].append(i)

start = 0
q = [start]
c[start] = True
while q:
    i = q.pop()
    for j in E[i]:
        if c[j]:continue
        c[j] = True
        q.append(j)

ans = True
for b in c[:N]:
    ans = ans and b
print("YES" if ans else "NO")