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
from networkx.utils import UnionFind
def input(): return sys.stdin.readline().rstrip()


def main():
    n,m=map(int, input().split())
    lang=[[] for i in range(m+1)]
    for i in range(1,n+1):
        for talk in list(map(int, input().split()))[1:]:
            lang[talk].append(i)
    uf = UnionFind()
    for langs in lang:
        if len(langs) >=1:
            uf.union(*langs)
    print('YES' if len(list(uf.to_sets()))==1 else 'NO')
    




if __name__ == '__main__':
    main()

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

class UnionFind():
    """unionFindツリー
    FindとUnionがきも
    https://note.nkmk.me/python-union-find/
    """
    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

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

uf = UnionFind(N+M)
for i in range(N):
  li = list(map(int, input().split()))
  for j in li[1:]:
    uf.union(i,N+j-1)
    
p = uf.find(0)
for i in range(1,N):
  q = uf.find(i)
  
  if p != q:
    print("NO")
    exit(0)
    
print("YES")

Solution (Python):
import sys

input = sys.stdin.readline


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

    def find(self, x):
        if self.parent[x] == x:
            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:
            if self.height[x] < self.height[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.height[x] == self.height[y]:
                    self.height[x] += 1

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


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

uf = UnionFind(M)
lang = set()
for _ in range(N):
    KL = tuple(map(int, input().split()))
    for i in range(1, KL[0]):
        uf.unite(KL[i] - 1, KL[i + 1] - 1)  
    for i in range(KL[0]):
        lang.add(KL[i + 1] - 1)

lang = list(lang)
print('YES' if uf.group_size(lang[0]) == len(lang) else 'NO')

Solution (Python):
class Union_Find():
    def __init__(self, num):
        self.par = [-1]*(num+1)
        self.siz = [1]*(num+1)

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

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

    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.siz[ry] += self.siz[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
        return

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

n, m = map(int, input().split())
lang = [[] for i in range(m+1)]
for i in range(n):
    l = list(map(int, input().split()))
    for j in range(l[0]):
        lang[l[j+1]].append(i)

tree = Union_Find(n)
for i in range(1, m+1):
    for j in range(len(lang[i])-1):
        tree.union(lang[i][j+1], lang[i][j])

if tree.size(0) == n:
    print("YES")
else:
    print("NO")

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

n, m = map(int, input().split())
row = []
col = []
for i in range(n):
    k, *l = map(int, input().split())
    row += [i] * k
    col += [e + n - 1 for e in l]

cost = [1] * len(row)

graph = csr_matrix((cost, (row, col)), shape=(n + m, n + m))
_, labels = connected_components(graph)

bl = (labels[:n] == labels[0]).all()
print("YES" if bl else "NO")

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


n, m = map(int, input().split())
l = []
for _ in range(n):
    k, *ls = map(int, input().split())
    l.append(ls)

uf = UnionFind(m)

for li in l:
    for e1, e2 in zip(li, li[1:]):
        e1 -= 1
        e2 -= 1
        uf.unite(e1, e2)

p = uf.find_set(l[0][0] - 1)
ans = "YES"
for e, *_ in l:
    if uf.find_set(e - 1) != p:
        ans = "NO"

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


n, m = map(int, input().split())
l = []
for _ in range(n):
    k, *ls = map(int, input().split())
    l.append(ls)

uf = UnionFind(m)

for li in l:
    for e1, e2 in zip(li, li[1:]):
        e1 -= 1
        e2 -= 1
        uf.unite(e1, e2)

p = uf.find_set(l[0][0] - 1)
ans = "YES"
for e, *_ in l:
    if uf.find_set(e - 1) != p:
        ans = "NO"

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def get_par(par, p):
    while par[p] != p:
        p = par[p]
    return par[p]

n,m = map(int, input().split())
lang = {}
for i in range(n):
    k,*l = map(int, input().split())
    for j in l:
        
        if j not in lang:
            lang[j] = []
        lang[j].append(i)


par = [i for i in range(n)]
for k,v in lang.items():
    if len(v) == 1:
        continue
    a = v[0]
    for i in range(1,len(v)):
        aa = get_par(par, a)
        bb = get_par(par, v[i])
        if aa == bb:
            continue
        
        if aa < bb:
            par[bb] = aa
        else:
            par[aa] = bb

ans = [get_par(par, i) for i in range(n)]
print('YES' if len(set(ans)) == 1 else 'NO')

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
N, M = map(int, input().split())
K = [0]*(N+1)
L = [[] for _ in range(N+1)]
graph = [[] for _ in range(N+M+1)]
for i in range(1, N+1):
    K[i], *L[i] = map(int, input().split())
    for lang in L[i]:
        graph[i].append(lang + N)
        graph[lang + N].append(i)

seen = [False] * (N+M+1)
person = [0] * (N+1)


def dfs(node, seen):
    here = node
    seen[here] = True
    
    if here <= N:
        person[here] = 1
    for goto in graph[here]:
        if not seen[goto]:
            dfs(goto, seen)


dfs(1, seen)
print("YES" if sum(person) == N else "NO")

Solution (Python):
n,m=map(int,input().split())
import sys;sys.setrecursionlimit(10**9)
class Union_Find():
  def __init__(self,n):self.n,self.r=[-1]*n,[0]*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,y=self.Find_Root(x),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;self.r[y]+=self.r[x]==self.r[y]
  def isRootSame(self,x,y):return self.Find_Root(x)==self.Find_Root(y)
  def Count(self,x):return -self.n[self.Find_Root(x)]
u=Union_Find(m)
l=[list(map(int,input().split()))for _ in range(n)]
for i in range(n):
  for j in range(1,len(l[i])-1):u.Unite(l[i][j]-1,l[i][j+1]-1)
for i in range(n-1):
  if not(u.isRootSame(l[i][1]-1,l[i+1][1]-1)):print("NO");exit()
print("YES")

Solution (Python):

def wantp(n):

    l = []
    while p[n] != n:
        l.append(n)
        n = p[n]

    for i in l:
        p[i] = n

    return n



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

dic = {}

for i in range(N):

    kl = list(map(int,input().split()))

    for j in range(kl[0]):

        j += 1
        if kl[j] not in dic:
            dic[kl[j]] = []

        dic[kl[j]].append(i)

p = [i for i in range(N)]
rank = [1] * N

for i in dic:

    if i not in dic:
        continue

    for j in range(len(dic[i]) - 1):

        a = dic[i][j]
        b = dic[i][j+1]

        ap = wantp(a)
        bp = wantp(b)

        if ap != bp:

            if rank[ap] > rank[bp]:
                p[bp] = ap
            elif rank[ap] < rank[bp]:
                p[ap] = bp
            else:
                p[ap] = bp
                rank[bp] += 1

n = 0
for i in range(N):
    if i == wantp(p[i]):
        n += 1


if n == 1:
    print ("YES")
else:
    print ("NO")

Solution (Python):
from functools import reduce

class UnionFind(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 = map(int, input().split())
l = [list(map(int, input().split()))[1:] for i in range(n)]
langs = [list() for i in range(m)]
for p,i in enumerate(l):
  for lang in i:
    langs[lang-1].append(p)
commu = UnionFind(n)
for i in langs:
  if i:
    now = i[0]
    for j in i[1:]:
      commu.union(now,j)
      now = j
if commu.get_size(0) == n:
  print("YES")
else:
  print("NO")

Solution (Python):
from collections import defaultdict

N, M = map(int, input().split())
V = range(N+M)
E = defaultdict(list)
for i in range(N):
    _, *L, = map(int, input().split())
    for l in L:
        l -= 1
        E[i].append(l+N)
        E[l+N].append(i)
stack = [0]
visited = [False] * (N+M)
while stack:
    i = stack.pop()
    if visited[i]: continue
    visited[i] = True
    for j in E[i]:
        if not visited[j]:
            stack.append(j)
if sum(visited[:N]) == N:
    print('YES')
else:
    print('NO')

Solution (Python):

class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]

N, M = map(int, input().split())
C = [False] * (M+1)
uf = Uf(M+1)
for _ in range(N):
    K, *L = map(int, input().split())
    l0 = L[0]
    C[l0] = True
    for l in L[1:]:
        uf.unite(l0, l)
        C[l] = True
roots = [uf.root(i) for i, c in enumerate(C) if c]
print("YES" if len(set(roots))==1 else "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 main():
    N, M = map(int, input().split())
    uni = UnionFind(N + M)
    for i in range(N):
        K, *L = map(int, input().split())
        for l in L:
            uni.union(i, N + l - 1)
    
    root = set()
    for i in range(N):
        root.add(uni.find(i))
    
    if len(root) == 1:
        print('YES')
    else:
        print('NO')



main()

Solution (Python):
n,m = map(int,input().split())
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())
uf = UnionFind(n)
people = [[]for i in range(m)]
for i in range(n):
    a = list(map(int,input().split()))
    n1 = a.pop(0)
    for j in range(n1):
        if len(people[a[j]-1]) == 0:
            people[a[j]-1].append(i)
        else:
            uf.union(people[a[j]-1][0],i)
if uf.group_count() == 1:
    print("YES")
else:
    print("NO")

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque

parent_node = []

def union_find(ele):
    global parent_node
    if parent_node[ele] != ele:
        parent_node[ele] = union_find(parent_node[ele])
    return parent_node[ele]

def main():
    num, lang_num = map(int, input().split())

    graph_data = defaultdict(set)
    for i in range(num):
        data = list(map(int, input().split()))
        for ele in data[1:]:
            graph_data[ele].add(i + 1)

    global parent_node
    parent_node = [i for i in range(num + 1)]




    for key, value in graph_data.items():
        min_set = set([union_find(ele) for ele in value])
        min_ind = min(list(min_set))
        for ele in min_set:
            parent_node[ele] = min_ind

    for i in range(num + 1):
        a = union_find(i)

    

    if max(parent_node) == 1:
        print('YES')
    else:
        print('NO')









if __name__ == '__main__':
    main()

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

    def root(self, x):
        """頂点xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """頂点xを含む集合と頂点y含む集合を結合する"""
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.parent[x] > self.parent[y]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        return

    def is_same(self, x, y):
        """頂点xと頂点yが同じ集合に属するかどうかを返す"""
        return self.root(x) == self.root(y)

    def get_size(self, x):
        '''頂点xを含む集合の要素数を返す'''
        return -self.parent[self.root(x)]


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

li = [[] for i in range(m)]
for i in range(n):
    for num in info[i][1:]:
        li[num - 1].append(i)

uf = UnionFind(n)
for li_ in li:
    for i in range(len(li_) - 1):
        if not uf.is_same(li_[i], li_[i + 1]):
            uf.merge(li_[i], li_[i + 1])

if uf.get_size(0) == n:
    print("YES")
else:
    print("NO")

Solution (Python):
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

class UnionFind :
    def __init__(self, size) :
        """
        Parameters
        ---
        size : int
            頂点数
        """
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        """
        親のインデックスの取得

        Parameters
        ---
        index : int
            取得する頂点のインデックス

        Returns
        ---
        rootIndex : int
            指定した頂点の根のインデックス
        """
        if self.parent[index] == index :  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2) :  
        """
        木の結合

        Parameters
        ---
        index1 : int
        index2 : int
            結合する頂点のインデックス
        """
        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) :
        """
        同じ木に属するかを判定する

        Parameters
        ---
        index1 : int
        index2 : int

        Returns
        ---
        boolean
        """
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        """
        指定した頂点の属する木の大きさを取得する
        """
        return self.size[self.root(index)]

    def getComponent(self) :
        """
        連結成分数を取得する
        """
        return self.component


def sol():
    N, M = map(int, input().split())

    tree = UnionFind(N + M)

    for person in range(N):
        line = list(map(int, input().split()))
        for lang in line[1:]:
            tree.union(person, N + lang - 1)

    rootList = set()
    for person in range(N):
        rootList.add(tree.root(person))

    if len(rootList) == 1:
        print('YES')
    else:
        print('NO')

sol()

Solution (Python):
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        
        if self._ranks[x] > self._ranks[y]:
            
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def root(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.root(x)]


N, M = list(map(int, sys.stdin.readline().split()))
uf = UnionFind(size=N + M + 1)
for i in range(N):
    _, *L = list(map(int, sys.stdin.readline().split()))
    for lang in L:
        uf.unite(i, N + lang)

ok = True
root = uf.root(0)
for i in range(N):
    ok &= root == uf.root(i)
if ok:
    print("YES")
else:
    print("NO")

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)




from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N,M = map(int,input().split())
row = []
col = []
for i in range(N):
    K,*L = map(int,input().split())
    row += [i] * K
    col += [x-1+N for x in L]

graph = csr_matrix(([1]*len(row), (row,col)), (N+M,N+M))

_,comp = connected_components(graph)

bl = (comp[:N] == comp[0]).all()

answer = 'YES' if bl else 'NO'
print(answer)

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:
            x, y = y, x
        self.v[x] += self.v[y]
        self.v[y] = x

    def root(self, x):
        return self.v[x] < 0

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

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


n, m = map(int, input().split())

uf = UnionFind(n + m)
for i in range(n):
    _, *lngs = map(int, input().split())
    for lng in lngs:
        uf.unite(i, n + lng - 1)

can = all(uf.same(j, n - 1) for j in range(n - 1))
print('YES' if can else 'NO')

Solution (Python):
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

n,m=map(int,input().split())
UF=UF(n+m)
for i in range(n):
  l=list(map(int,input().split()))
  for j in range(1,l[0]+1):
    UF.unite(i,n+l[j]-1)
ct=0
for i in range(n,n+m):
  if UF.size(i)==1:
    ct+=1
if UF.groupnum()-ct==1:
  print('YES')
else:
  print('NO')

Solution (Python):
N, M = map(int, input().split())
People = [[] for i in range(N)]
Language = [[] for i in range(M)]
for i in range(N):
    language = list(map(int, input().split()))[1:]
    for l in language:
        l -= 1
        People[i].append(l)
        Language[l].append(i)


people_visited = [False] * N
language_visited = [False] * M


stack = [(0, 'people')]
while stack:
    n, n_type = stack.pop()

    if n_type == 'people':
        people_visited[n] = True
        for to in People[n]:
            if language_visited[to]:
                continue
            stack.append((to, 'language'))

    elif n_type == 'language':
        language_visited[n] = True
        for to in Language[n]:
            if people_visited[to]:
                continue
            stack.append((to, 'people'))

print('YES' if all(people_visited) else 'NO')

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from functools import reduce

class UnionFind:
    def __init__(self, node: int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]

    def find(self, x: int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> bool:
        if self.isSame(x, y):
            
            return False

        rx = self.find(x)
        ry = self.find(y)

        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]

            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

        return True

    def isSame(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


n, m = li()
lang = [[] for _ in range(m)]
for person in range(n):
    kl = list(li_())
    for langi in kl[1:]:
        lang[langi].append(person)

uf = UnionFind(n)
for langi in lang:
    if len(langi) < 2:
        continue

    for i in range(len(langi)-1):
        uf.unite(langi[i], langi[i+1])


for i in range(n):
    uf.find(i)

ok = True
for i in range(1, n):
    if uf.isSame(0, i):
        continue

    else:
        ok = False
        break

print("YES" if ok else "NO")

Solution (Python):
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]
  
n,m=map(int,input().split())
t=UnionFind(n+m)
for i in range(n):
  l=list(map(int,input().split()))
  for j in range(l[0]):
    t.Unite(i+1,n+l[1+j])
s=set()
for i in range(n):
  r=t.FindRoot(i+1)
  s.add(r)
if len(s)==1:
  print('YES')
else:
  print('NO')