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.table = [-1] * n

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def unite(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.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def get_size(self, x):
        return -self.table[self._root(x)]


n, m = map(int, input().split())
uft = UnionFind(n + m)
for i in range(n):
    k, *lll = map(int, input().split())
    for l in lll:
        uft.unite(i, l + n - 1)

for j in range(1, n):
    if not uft.find(0, j):
        print('NO')
        break
else:
    print('YES')

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
うーん，二部グラフっぽい？
言語と人の対応で，パスが8以内にあればOKみたいな
木の直径みたいな感じで行ける？
ある人から見て一番遠い人を1人選んで，その人から見て全員が8以内に入ればOKそう？
誤読っぽ，単純にUFで良いかも
"""

def main():
    
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        重いかも！　　members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        重いかも！　all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        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=MI()
    uf=UnionFind(N+M)
    for i in range(N):
        L=LI()
        for j in range(1,L[0]+1):
            l=L[j]
            l-=1
            uf.union(i,l+N)
            
    roots=uf.roots()
    temp=0
    for v in roots:
        if v<N:
            temp+=1
        
            
    if temp<=1:
        print("YES")
    else:
        print("NO")
        

        
            
    
main()

Solution (Python):
from collections import deque

def bfs():
    global ok
    q = deque()
    q.append(1)
    ok[1] = 1
    while q:
        i = q.popleft()
        for j in G[i]:
            if ok[j] == 0:
                ok[j] = 1
                q.append(j)
    return

n, m = map(int, input().split())
G = [[] for _ in range(200001)]
for x in range(1, n + 1):
    l = list(map(int, input().split()))
    for i in range(1, l[0] + 1):
        y = l[i] + 100000
        G[x].append(y)
        G[y].append(x)
ok = [0] * 200001
bfs()
print("YES" if sum(ok[1 : n + 1]) == n else "NO")

Solution (Python):
n,m=map(int,input().split())
l=[]
k=[]
g=set(())
d={}
cnt=0
for i in range(n):
  tmp=list(map(int,input().split()))
  k.append(tmp[0])
  l.append(tmp[1:])
  for j in tmp[1:]:
    if j in d:
      pass
    else:
      d[j]=cnt
      cnt+=1
mi=d.keys()

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(len(mi))
for li in l:
  if len(li)==1:continue
  for x in li[1:]:
    uf.union(d[li[0]],d[x])
if uf.group_count()>1:
  print('NO')
else:
  print('YES')

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(self.roots())

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



n, m = (int(x) for x in input().split())
L = [tuple(int(x) for x in input().split()) for _ in range(n)]

uf = UnionFind(n + m)
for i in range(n):
    for l in L[i][1:]:
        l -= 1
        uf.union(i, n + l)

roots = uf.roots()
if len(roots) == 1 or roots[1] >= n:
    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(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個の要素を0 ~ n - 1の番号で管理する。以下の属性およびメソッドを持つ。

    parents
    各要素の親要素の番号を格納するリスト
    要素が根（ルート）の場合は-(そのグループの要素数)を格納する

    find(x)
    要素xが属するグループの根を返す

    union(x, y)
    要素xが属するグループと要素yが属するグループとを併合する

    size(x)
    要素xが属するグループのサイズ（要素数）を返す

    same(x, y)
    要素x, yが同じグループに属するかどうかを返す

    members(x)
    要素xが属するグループに属する要素をリストで返す

    roots()
    すべての根の要素をリストで返す

    group_count()
    グループの数を返す

    all_group_members
    {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す

    __str__()
    print()での表示用
    ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
    """


n, m = (int(x) for x in input().split())
L = [set() for _ in range(n)]
for i in range(n):
    k, *arg = (int(x) for x in input().split())
    L[i].update(set(arg))

ANS = L[0]
uf = UnionFind(n)
for _ in range(100):
    for i in range(1, n):
        if ANS & L[i]:
            ANS |= L[i]
            uf.union(0, i)
    for i in reversed(range(1, n)):
        if ANS & L[i]:
            ANS |= L[i]
            uf.union(0, i)

if uf.group_count() == 1:
    print("YES")
else:
    print("NO")

Solution (Python):
N,M=map(int,input().split())
belong=list()
group=list()

def init(X):
  global belong,group
  belong=list(range(X))
  group=[[i] for i in range(X)]

def unite(x,y):
  global belong,group
  if len(group[belong[x]])<len(group[belong[y]]):
    x,y=y,x
  if belong[x]==belong[y]:
    return True
  z=belong[y]
  for i in range(len(group[z])):
    belong[group[z][-1]]=belong[x]
    group[belong[x]].append(group[z][-1])
    del group[z][-1]
  return False

init(N+M)
L=[]
for i in range(N):
  L=list(map(int,input().split()))
  for j in range(L[0]):
    unite(i,L[j+1]+N-1)
if len(set(belong[:N]))==1:
  print('YES')
else:
  print('NO')

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dfs(v):
        for u in edge[v]:
            if visited[u]:
                continue
            else:
                visited[u] = True
                dfs(u)

    n, m = map(int, input().split())
    edge = [[] for _ in range(n + m)]
    for i in range(n):
        _, *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)
    dfs(0)
    for i in range(n):
        if not visited[i]:
            print("NO")
            break
    else:
        print("YES")


if __name__ == '__main__':
    resolve()

Solution (Python):

"""
グラフが連結であるかどうかを判定せよ？
距離が2以下になっているか判定せよかと思ったが、つながってればいいっぽい？
dfsで全部回れば良い
"""
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m = map(int,readline().split())
g = [[] for i in range(m)] 
h = [] 
for i in range(n):
    lst1 = list(map(int,readline().split()))
    lst1 = lst1[1:]
    for j in lst1:
        g[j-1].append(i)
    h.append(lst1)


check = [0]*n
language = [0]*m
root = 0
check[root] = 1
deq = deque([root])
while deq:
    fr = deq.pop()
    for i in h[fr]:
        if language[i-1]:
            continue
        language[i-1] = 1
        for j in g[i-1]:
            if check[j]:
                continue
            deq.append(j)
            check[j] = 1


if all(i==1 for i in check):
    print("YES")
else:
    print("NO")

Solution (Python):
from networkx import*
print('YES'*is_connected(Graph((i,j)for i in[*open(0)][1:]for j in i.split()[1:]))or'NO')

Solution (Python):
from networkx import*
print('NYOE S'[is_connected(Graph((t,j)for t in[*open(0)][1:]for j in t.split()[1:]))::2])

Solution (Python):
from networkx import*
print('NYOE S'[is_connected(Graph((i,j)for i,t in[*enumerate(open(0))][1:]for j in t.split()[1:]))::2])

Solution (Python):
from networkx import*
print('NYOE S'[is_connected(Graph([(i,j)for i,t in[*enumerate(open(0))][1:]for j in t.split()[1:]]))::2])

Solution (Python):
from networkx import*
g=[]
for t in[*open(i:=0)][1:]:
 i+=1
 for j in t.split()[1:]:g+=(i,j),
print('NYOE S'[is_connected(Graph(g))::2])

Solution (Python):
from networkx import*
g=[]
for t in[*open(i:=0)][1:]:
 for j in t.split()[1:]:g+=(i,'!'+j),
 i+=1
print('NYOE S'[is_connected(Graph(g))::2])

Solution (Python):
from networkx import*
g=[]
for _,*t in[*map(str.split,open(i:=0))][1:]:
 for j in t:g+=(i,'!'+j),
 i+=1
print('NYOE S'[is_connected(Graph(g))::2])

Solution (Python):
N,M=map(int,input().split())  

par=[i for i in range(N+M)]
rank=[0]*(N+M)
friend=[0]*(N+M)
block=[0]*(N+M)
size=[1]*(N+M)

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


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

def union(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return 
  if rank[x]>rank[y]:
    par[y]=x
    size[x]+=size[y]
  else:
    par[x]=y
    size[y]+=size[x]
    if rank[x]==rank[y]:
      rank[y]+=1


for i in range(N):
  A=list(map(int, input().split()))
  a=A[0]
  A=A[1:]
  for j in A:
    union(i,N+j-1)
D=[]
for i in range(N):
  D.append(find(i))
if len(set(D))==1:
  print('YES')
else:
  print('NO')

Solution (Python):

import sys
from typing import Iterable
def main(N, M, KL):
    uf = UnionFindTree(N + M)
    for i, (K, *L) in enumerate(KL):
        for l in L:
            uf.union(i, N + l - 1)
    print('YES' if uf.same_all(range(N)) else 'NO')

class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.parent = [-1] * n

    def find(self, x: int) -> int:
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x: int, y: int) -> bool:
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

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

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

    def same_all(self, indices: Iterable[int]) -> bool:
        f, v = self.find, self.find(indices[0])
        return all(f(i) == v for i in indices)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    KL = [list(map(int, input().split())) for _ in range(N)]
    main(N, M, KL)

Solution (Python):

from typing import Iterable
import sys
def main(N, M, KL):
    uf = UnionFindTree(N + M)
    for i, (K, *L) in enumerate(KL):
        for l in L:
            uf.union(i, N + l - 1)
    print('YES' if uf.same_all(range(N)) else 'NO')

class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.parent = [-1] * n

    def find(self, x: int) -> int:
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x: int, y: int) -> bool:
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

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

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

    def same_all(self, indices: Iterable) -> bool:
        f, v = self.find, self.find(indices[0])
        return all(f(i) == v for i in indices)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    KL = [list(map(int, input().split())) for _ in range(N)]
    main(N, M, KL)

Solution (Python):

import sys
def main(N, M, KL):
    uf = UnionFindTree(N + M)
    for i, (K, *L) in enumerate(KL):
        for l in L:
            uf.union(i, N + l - 1)
    g = uf.find(0)
    for i in range(1, N):
        if uf.find(i) != g:
            break
    else:
        print('YES')
        return
    print('NO')

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

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

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

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    KL = [list(map(int, input().split())) for _ in range(N)]
    main(N, M, KL)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

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

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

    
    
n, m = map(int, input().split())
lang = []
for _ in range(n):
    a = [int(i) for i in input().split()[1:]]
    lang.append(a)    
un = UnionFind(n + m)

for i in range(n):
    for l in lang[i]:
        un.union(i, l + n)

ans = set([])
for i in range(n):
    k = un.find(i)
    ans.add(k)
    
if len(ans) == 1:
    print('YES')
else:
    print('NO')

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

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

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

    
    
n, m = map(int, input().split())
lang = []
for _ in range(n):
    a = [int(i) for i in input().split()[1:]]
    lang.append(a)    
un = UnionFind(n + m)

for i in range(n):
    for l in lang[i]:
        un.union(i, l + n)

ans = set([])
for i in range(n):
    k = un.find(i)
    ans.add(k)
    
if len(ans) == 1:
    print('YES')
else:
    print('NO')

Solution (Python):
from collections import deque
import sys
from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            
            
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   
            self.parent[x] = y      
            return self.parent[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        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 weighted_union(self, x, y, w):
        
        px = self.find(x)
        py = self.find(y)
        
        
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = - w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] =  w + self.weight[x] - self.weight[y]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0

    
    def judge(self, x, y):
        return self.find(x) == self.find(y)
input = sys.stdin.readline
n, m = map(int, input().split())
langs = [[] for i in range(m)]
for i in range(n):
    inputs = list(map(int, input().split()))
    k = inputs[0]
    ls = inputs[1:]
    for l in ls:
        langs[l-1].append(i)

uf = UnionFind(n)
for l in langs:
    if len(l) <= 1: continue
    x = l[0]
    for y in l[1:]:
        if not uf.judge(x, y): uf.union(x, y)

ans = set()
for i in range(n):
    ans.add(uf.find(i))
if len(ans) == 1:
    print("YES")
else:
    print("NO")

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



class UnionFindTree:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.size = [1] * n

    def root(self, i):
        inter = set()
        while self.parent[i]!=i:
            inter.add(i)
            i = self.parent[i]
        r = i
        for i in inter:
            self.parent[i] = r
        return r

    def connect(self, i, j):
        if i==j:
            return
        ri = self.root(i)
        rj = self.root(j)
        if ri==rj:
            return
        if self.size[ri]<self.size[rj]:
            self.parent[ri] = rj
            self.size[rj] += self.size[ri]
        else:
            self.parent[rj] = ri
            self.size[ri] += self.size[rj]

n,m = map(int, input().split())
d = {i: [] for i in range(m)}
for i in range(n):
    l = list(map(lambda x: int(x)-1, input().split()))
    for j in l[1:]:
        d[j].append(i)
uf = UnionFindTree(n)
for item in d.values():
    if len(item)>=2:
        for u in item:
            uf.connect(item[0], u)
for i in range(n):
    uf.root(i)
if all(uf.parent[0] == item for item in uf.parent):
    print("YES")
else:
    print("NO")

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)

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

uf = UnionFind(m+1) 

lastcheck=set([])
klkl=[]
for _ in range(n):
    kl=list(map(int,input().split()))[1:]
    if len(kl)>1:
        for item in kl[1:]:
            uf.union(kl[0]-1,item-1)
    klkl.append(kl)
uf_list=uf.members(klkl[0][0]-1)

flag=0
for kl in klkl:
    for item in kl:
        item-=1
        if item not in uf_list:
            flag=1
        else:
            break
if flag==1:
    print("NO")
else:
    print("YES")

Solution (Python):
N, M = [int(x) for x in input().split()]
KL = [[int(x) for x in input().split()] for _ in range(N)]


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


u = UnionFind(N + M)

for i, (kl) in enumerate(KL):
    for j, k in enumerate(kl):
        if j == 0:
            continue
        u.union(i, k + N - 1)

v = set()
for i in range(N):
    v.add(u.find(i))

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

Solution (Python):
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]

from collections import defaultdict
d = defaultdict(lambda: [])
for i,ls in enumerate(L):
    for l in ls[1:]:
        d[l].append(i)

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

uf = UnionFind(N)

for ls in d.values():
    for a,b in zip(ls,ls[1:]):
        if uf.is_same(a,b): continue
        uf.unite(a,b)

print('YES' if uf.size(0)==N else 'NO')

Solution (Python):
class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n
    
    def root(self,x):
        if self.par[x] == -1:
            return x 
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x_r = self.root(x)
        y_r = self.root(y)
        
        if self.rank[x_r]>self.rank[y_r]:
            self.par[y_r] = x_r

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

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

    def size(self,x):
        return self.tsize[self.root(x)]
      
n,m = tuple(map(int,input().split()))

ll = []
uf = UnionFind(m)
for _ in range(n):
  k, *l = tuple(map(int,input().split()))
  for i in range(k-1):
    uf.unite(l[i]-1,l[i+1]-1)
  ll.append(l[0]-1)

for lang in ll:
  if not uf.isSame(lang,ll[-1]):
    print("NO")
    exit()
print("YES")

Solution (Python):
from collections import deque
"""
https://tjkendev.github.io/procon-library/python/graph/bfs.html
"""
def bfs(G):
    dist = [-1]*(N+M)
    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)
    
    return dist

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

graph = [[] for _ in range(N+M)]

for i in range(N):
    KL = list(map(int,input().split()))
    for j in KL[1:]:
        graph[i].append(N+j-1)
        graph[N+j-1].append(i)

ans = bfs(graph)

if -1 in ans[:N]:
    print("NO")
else:
    print("YES")

Solution (Python):
class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n
    
    def root(self,x):
        if self.par[x] == -1:
            return x 
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x_r = self.root(x)
        y_r = self.root(y)
        
        if self.rank[x_r]>self.rank[y_r]:
            self.par[y_r] = x_r

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

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

    def size(self,x):
        return self.tsize[self.root(x)]
      
n,m = tuple(map(int,input().split()))

ll = []
uf = UnionFind(m)
for _ in range(n):
  k, *l = tuple(map(int,input().split()))
  for i in range(k-1):
    uf.unite(l[i]-1,l[i+1]-1)
  ll.append(l[0]-1)

for lang in ll:
  if not uf.isSame(lang,ll[-1]):
    print("NO")
    exit()
print("YES")