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):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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


n, m = map(int, input().split())
uf = UnionFind(n + m)

for i in range(n):
    k, *L = map(int, input().split())
    for l in L:
        uf.union(l - 1, m + i)

for i in range(n - 1):
    if not uf.same(m + i, m + i + 1):
        print("NO")
        break
else:
    print("YES")

Solution (Python):
from collections import deque

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

edge = [[] for _ in range(N + M)]
for i in range(N):
    K,*L = map(int, input().split())
    for l in L:
        edge[i].append(N + l - 1)
        edge[N + l - 1].append(i)

visited = [False] * (N + M)
visited[0] = True
que = deque([0])
while que:
    v = que.popleft()

    for w in edge[v]:
        if visited[w]: continue
        visited[w] = True
        que.append(w)
    
flag = True
for i in range(N):
    if not visited[i]:
        flag = False

if flag:
    print('YES')
else:
    print('NO')

Solution (Python):
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2) :  
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  
            return

        self.component -= 1  

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

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

tree = UnionFind(N + M)

for i in range(N):
    L = tuple(map(int, input().split()))
    for l in L[1:]:
        tree.union(i, N + l - 1)

V = set()
for i in range(N):
    V.add(tree.root(i))

print('YES' if len(V) == 1 else 'NO')

Solution (Python):
import sys;sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
    self.siz=n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
    self.siz-=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]
  def size(self):
    return self.siz
n,m=map(int,input().split())
u=UnionFind(m+1)
ll=set()
for i in range(n):
  k,*l=map(int,input().split())
  if i==0:root=l[0]
  for j in range(len(l)-1):u.unite(l[j],l[j+1])
  ll|=set(l)
if len(ll)==u.count(root):print('YES')
else:print('NO')

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.rank = [1] * n

    def get_root(self, i):
        while self.parent[i] != -1:
            i = self.parent[i]
        return i

    def is_same_tree(self, i, j):
        return self.get_root(i) == self.get_root(j)

    def merge(self, i, j):
        i = self.get_root(i)
        j = self.get_root(j)
        if i == j:
            return

        if self.rank[i] > self.rank[j]:
            self.parent[j] = i
            self.rank[i] = max(self.rank[i], self.rank[j] + 1)
        else:
            self.parent[i] = j
            self.rank[j] = max(self.rank[j], self.rank[i] + 1)

n, m = [int(i) for i in input().split()]
l = [[] for _ in range(m)]
for i in range(n):
    kl = [int(i)-1 for i in input().split()]
    for j in kl[1:]:
        l[j].append(i)
uf = UnionFind(n)
for i in l:
    for j in range(len(i) - 1):
        uf.merge(i[j], i[j + 1])

for i in range(n - 1):
    if not uf.is_same_tree(i, i + 1):
        print("NO")
        break
else:
    print("YES")

Solution (Python):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for _ in range(N)]
    EdgeK = [[] for _ in range(M)]
    for i in range(N):
        L = [int(j) for j in input().split()]
        for j in L[1:]:
            Edge[i].append(j - 1)
            EdgeK[j - 1].append(i)

    Visited = [False] * N
    VK = [False] * M
    q = deque()
    q.append((0, 0)) 

    while q:
        nN, nT = q.pop()
        if nT == 0: 
            if not Visited[nN]:
                Visited[nN] = True
                for ne in Edge[nN]:
                    if not VK[ne]: q.append((ne, 1))
        else:
            if not VK[nN]:
                VK[nN] = True
                for ne in EdgeK[nN]:
                    if not Visited[ne]: q.append((ne, 0))
    if False in Visited: print("NO")
    else: print("YES")


    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
n, m = map(int, input().split())

from collections import defaultdict

G = defaultdict(list)

for i in range(n):
    ll = list(map(int, input().split()))[1:]
    for l in ll:
        G[l + n - 1].append(i)
        G[i].append(l + n - 1)



from collections import deque

dist = [-1] * (n + m + 1)
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

if -1 in dist[:n]:
    print("NO")
else:
    print("YES")

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

class UnionFind:
    def __init__(self, n):
        
        
        self.table = [-1] * n
        self.size = [1] * n
        self.group_num = n

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

    def get_size(self, x):
        r = self.root(x)
        return self.size[r]

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

    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
        self.group_num -= 1



n, m = LI()
lan = [[] for _ in range(m)]
uf = UnionFind(n)
for j in range(n):
    L = LI()
    k = L[0]
    for i in range(1, k + 1):
        lan[L[i] - 1] += [j]


for ll in lan:
    for s in range(len(ll)):
        uf.union(ll[s], ll[s - 1])

if uf.group_num == 1:
    print('YES')
else:
    print('NO')

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            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
        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 same(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int, input().split())
L = [list(map(int, input().split()))[1:] for _ in range(N)]
uf = UnionFind(M+1)
used = [False] * (M+1)
for i in range(N):
    u = L[i][0]
    used[u] = True
    for v in L[i][1:]:
        used[v] = True
        uf.unite(u, v)
root = set()
for v in range(1, M+1):
    if used[v]:
        root.add(uf.find(v))
if len(root) == 1:
    print('YES')
else:
    print('NO')

Solution (Python):
import sys
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

readline = sys.stdin.readline

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

a = []
b = []
for i in range(M + 1, M + N + 1):
    K, *L = map(int, readline().split())
    l = len(L)
    a.extend([i] * l)
    b.extend(L)

m = csr_matrix(([1] * len(a), (a, b)), shape=(N + M + 1, N + M + 1))
n, label = connected_components(m, directed=False)
if all(label[1 + M:] == label[1 + M]):
    print('YES')
else:
    print('NO')

Solution (Python):
import sys
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
import numpy as np

readline = sys.stdin.readline

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

a = []
b = []
for i in range(M + 1, M + N + 1):
    K, *L = map(int, readline().split())
    l = len(L)
    a.extend([i] * l)
    b.extend(L)

m = csr_matrix(([1] * len(a), (a, b)), shape=(N + M + 1, N + M + 1))
n, label = connected_components(m, directed=False)
if np.all(label[1 + M:] == label[1 + M]):
    print('YES')
else:
    print('NO')

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return (i for i in range(self.N) if self.find(i) == root)

    def roots(self):
        return (i for i, x in enumerate(self.parents) if x < 0)

    def group_count(self):
        return len(list(self.roots()))

    def all_group_members(self):
        dic = {}
        for x in range(self.N):
            r = self.find(x)
            dic.setdefault(r, [])
            dic[r].append(x)
        return dic

import sys
input=sys.stdin.readline
def main():
    N,M=map(int, input().split())
    L=[list(map(int, input().split()))[1:]for _ in range(N)]
    UF=UnionFind(N+M)
    for i in range(N):
        for l in L[i]:
            UF.union(i,N+l-1)
    b=set(i for i in UF.members(0) if i < N)==set(range(N))
    print("YNEOS"[not b::2])

if __name__ == "__main__":
    main()

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m= map(int, input().split())
a= [list(map(int, input().split())) for i in range(n)]
uf=UnionFind(m)
x=[0]*m
for i in range(n):
    if a[i][0]==1:
        x[a[i][1]-1]=1
    else:
        for j in range(1,len(a[i])-1):
            uf.union(a[i][j]-1,a[i][j+1]-1)
            if x[a[i][j]-1]==0:
                x[a[i][j]-1]=1
            if j==len(a[i])-2:
                if x[a[i][j+1]-1]==0:
                    x[a[i][j+1]-1]=1

for i in range(m):
    if x[i]==0:
        if i==m-1:
            uf.union(m-1,0)
        else:
            uf.union(i,i+1)

y=uf.group_count()
if y==1:
    print('YES')

else:
    print('NO')

Solution (Python):
N,M = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(N)]

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

uf = UnionFind(N+M)
for i in range(N):
    for j in range(1, L[i][0]+1):
        uf.unite(i+M+1, L[i][j])

ans = "YES"
for i in range(M+1, M+N+1):
    if uf.isSameGroup(M+1, i):
        continue
    ans = "NO"
    break

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
edge = [[] for _ in range(N + M + 1)]
for i in range(N):
    i += M + 1
    k, *L = map(int, input().split())
    for l in L:
        edge[i].append(l)
        edge[l].append(i)



pair = [-1] * (N + M + 1)

cnt = 1
for i in range(1, N + M + 1):
    if pair[-1] == -1:
        node = [i]
        pair[i] = cnt
        while node:
            s = node.pop()
            for t in edge[s]:
                if pair[t] == -1:
                    pair[t] = cnt
                    node.append(t)
        cnt += 1

tmp = pair[M + 1]
ans = "YES" if all(tmp == i for i in pair[M + 1:]) else "NO"
print(ans)

Solution (Python):
from itertools import *
import copy
N,M=map(int,input().split())
KL=[list(map(int,input().split())) for i in range(N)]

human=[set() for i in range(N+1)]
gengo=[set() for i in range(M+1)]
for i in range(N):
    for m in range(1,KL[i][0]+1):
        human[i].add(KL[i][m])
        gengo[KL[i][m]].add(i)

usedhuman=set([1])
usedgengo=set(human[1])
stack=[i for i in human[1]]
while stack:
    g=stack.pop()
    for h in gengo[g]:
        if not h in usedhuman:
            usedhuman.add(h)
            for ng in human[h]:
                if not ng in usedgengo:
                    usedgengo.add(ng)
                    stack.append(ng)

if len(usedhuman)==N:
    print("YES")
else:
    print("NO")

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def ufinit(n):
  global ufsz, ufances
  ufsz = [1] * n
  ufances = [0] * n
  for i in range(n):
    ufances[i] = i

def ufroot(x):
  global ufances
  a = []
  y = x
  while ufances[y] != y:
    a.append(y)
    y = ufances[y]
  for z in a:
    ufances[z] = y
  return y

def ufconn(x,y):
  global ufsz, ufances
  i = ufroot(x)
  j = ufroot(y)
  if i==j:
    return
  
  k  = j if (ufsz[i]<ufsz[j]) else i
  if k==j:
    ufances[i] = j
  else:
    ufances[j] = i
  ufsz[k] = ufsz[i] + ufsz[j]

n,m = inm()
k = []
l = []
for i in range(n):
    z = inl()
    k.append(z[0])
    l.append(z[1:])
ufinit(n+m)
for i in range(n):
    for j in l[i]:
        ufconn(i,j+n-1)
r = ufroot(0)
for i in range(1,n):
    if ufroot(i)!=r:
        print('NO')
        exit()
print('YES')

Solution (Python):
class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

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

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return
N,M=map(int,input().split())
G=unionFind(M)
s=set()
for i in range(N):
  tmp=tuple(map(int,input().split()))
  s.add(tmp[1]-1)
  for x in tmp[2:]:
    G.unite(tmp[1],x)

parent=set()
for i in s:
  parent.add(G.root(i))

if len(parent)==1:
  print("YES")
else:
  print("NO")

Solution (Python):
from collections import deque

n,m = map(int,input().split())
edges_p = {}
edges_l = {}

for i in range(1,m+1):
    edges_l[i] = []

for i in range(1,n+1):
    tmp = list(map(int, input().split()))
    edges_p[i] = tmp[1:]
    for j in edges_p[i]:
        edges_l[j].append(i)


remains = set(range(1,n+1))
remains_l = set(range(1,m+1))
d = deque()

d.append(1)
remains.remove(1)

while(len(d) > 0):
    tmp = d.pop()
    for i in edges_p[tmp]:
        if i in remains_l:
            for j in edges_l[i]:
                if j in remains:
                    d.append(j)
                    remains.remove(j)
            remains_l.remove(i)

if(len(remains) == 0):
    print('YES')
else:
    print('NO')

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



from itertools import combinations


class UF(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        '''
        x が属するグループを探索
        '''
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        '''
        x と y のグループを結合
        '''
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        '''
        x と y が同じグループか否か
        '''
        return self.find(x) == self.find(y)

    def get_size(self, x):
        '''
        x が属するグループの要素数
        '''
        x = self.find(x)
        return self.size[x]

N,M = LI()
uf = UF(N+M)
for i in range(N):
    kl = LI()
    for l in kl[1:]:
        uf.union(i,N+l-1)

root = uf.find(0)
for i in range(1,N):
    now = uf.find(i)
    if now != root:
        print('NO')
        exit()
print('YES')

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N,M = map(int,input().split())
    lang = [[] for _ in range(M)]
    for i in range(N):
        info = list(map(int,input().split()))
        info.pop(0)
        for num in info:
            lang[num-1].append(i)

    con = [[] for _ in range(N)]
    for s in lang:
        l = len(s)
        if l>1:
            for i in range(l-1):
                con[s[i]].append(s[i+1])
                con[s[i+1]].append(s[i])

    go = [False for _ in range(N)]
    go[0] = True
    que = deque([0])
    while que:
        now = que.pop()
        for fol in con[now]:
            if go[fol]:
                continue
            else:
                que.append(fol)
                go[fol] = True
                
    print("YES" if all(go) else "NO")

if __name__ == "__main__":
    main()

Solution (Python):













import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  

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

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        
        
        
        if root_x != root_y:
            
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root

def main():
    N,M = MI()

    """
    全員が誰かと言語で話せて、それが連結ならOK
    """
    uf=UnionFind(N+M)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes

    for i in range(N):
        _,*L = MI_()
        for l in L:
            unite(l+N, i)
    
    r = get_root(0)
    for i in range(N):
        if r!=get_root(i):
            print("NO")
            return

    print("YES")

if __name__ == '__main__':
    main()

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,m=map(int,input().split())
tree = UnionFind(n+m+1) 
for i in range(n):
  l=list(map(int,input().split()))
  for j in range(1,len(l)):
    tree.unite(i,l[j]+n)
rt=tree.find(0)

for i in range(1,n):
  
  if rt!= tree.find(i):
    print("NO");exit()
print("YES")

Solution (Python):
from collections import deque
N,M = map(int,input().split())
G = {}
for i in range(1,N+1):
    L = list(map(int,input().split()))
    G[i] = [L[j]+10**5 for j in range(1,L[0]+1)]
    for j in range(1,L[0]+1):
        if L[j]+10**5 not in G:
            G[L[j]+10**5] = []
        G[L[j]+10**5].append(i)
hist = [0 for _ in range(2*10**5+1)]
hist[1] = 1
que = deque([1])
while que:
    x = que.popleft()
    for y in G[x]:
        if hist[y]==0:
            que.append(y)
            hist[y] = 1
flag = 1
for i in range(1,N+1):
    if hist[i]==0:
        flag = 0
        break
if flag==1:
    print("YES")
else:
    print("NO")

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
from collections import defaultdict
INF = float("inf")


def yes():
    print("YES")  


def no():
    print("NO")  


class UnionFind(object):

    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def main():

    N, M = map(int, input().split())
    L = [0]*N
    lang_leader = defaultdict(int)
    for i in range(N):
        K, *L[i] = list(map(int, input().split()))
    
    uf = UnionFind(N+1)
    for i in range(N):
        for l in L[i]:
            if lang_leader[l] == 0:
                lang_leader[l] = i+1
            else:
                uf.unite(i, lang_leader[l]-1)

    
    
    flag = True
    for i in range(N):
        if not uf.same(0, i):
            flag = False
            break
    if flag:
        yes()
    else:
        no()

    pass


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
n, m = map(int,input().split())
B = [list(map(int,input().split())) for i in range(n)]
max_m = -1
for i in range(n):
    for j in range(1, len(B[i])):
        max_m = max(max_m, B[i][j])

C = [[] for i in range(max_m + 1)]
for i in range(n):
    for j in range(1, len(B[i])):
        C[B[i][j]].append(i)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def size(self, x):
        if self.parents[x] < 0:
            return -self.parents[x]
        else:
            self.parents[x] = self.size(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def n_cc(self):  
        A = [i for i in self.parents if i < 0]
        return len(A)

U = UnionFind(n)


for i in range(len(C)):
    for j in range(len(C[i])-1):
        
        U.union(C[i][j], C[i][j+1])



if U.n_cc() == 1:
    print("YES")
else:
    print("NO")