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.



Sample input:
4 6
3 1 2 3
2 4 2
2 4 6
1 6


Sample output:
YES

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()


def solve():
    N, M = nm()
    uf = UnionFind(M)
    lang_spoken = set()
    for i in range(N):
        k, *lang = nm()
        assert len(lang) == k
        roots = {uf.find(l - 1) for l in lang}
        lang_spoken |= roots
        rit = iter(roots)
        x = next(rit)
        for y in rit:
            uf.union(x, y)
    lang1 = next(iter(lang_spoken))
    return uf.size(lang1) == len(lang_spoken)


class UnionFind:
    def __init__(self, n):
        # total number of nodes.
        self.n = n
        # node id -> root node id
        self._root_table = list(range(n))
        # root node id -> group size
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            # Update the cache on query.
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # Ensure that x is the larger (or equal) group.
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

    def size(self, x):
        return self._size_table[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._root_table) if x == i]

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


print(["NO", "YES"][solve()])

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()


def solve():
    N, M = nm()
    uf = UnionFind(M)
    lang_spoken = set()
    for i in range(N):
        k, *lang = nm()
        assert len(lang) == k
        roots = {uf.find(l - 1) for l in lang}
        lang_spoken |= roots
        roots = list(roots)
        x = roots[0]
        for y in roots[1:]:
            uf.union(x, y)
    lang1 = next(iter(lang_spoken))
    return uf.size(lang1) == len(lang_spoken)


class UnionFind:
    def __init__(self, n):
        # total number of nodes.
        self.n = n
        # node id -> root node id
        self._root_table = list(range(n))
        # root node id -> group size
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            # Update the cache on query.
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # Ensure that x is the larger (or equal) group.
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

    def size(self, x):
        return self._size_table[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._root_table) if x == i]

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


print(["NO", "YES"][solve()])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
n, m = map(int, input().split())
# 人: 0~n, 言語:n~n+m
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+m)
for i in range(n):
    _, *l = list(map(int, input().split()))
    for lang in l:
        uf.union(i, n+lang-1)

f = True
for i in range(1, n):
    if not uf.same(0, i):
        f = False
if f:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
import sys

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, sys.stdin.readline().strip().split())

# 言語iを使える人のリスト
langs = [[] for _ in range(M)]
for i in range(N):
    tmp = list(map(int, sys.stdin.readline().strip().split()))
    K = tmp[0]
    L = tmp[1:]
    for l in L:
        langs[l-1].append(i)

# print(langs)
uf = UnionFind(N)
for peoples in langs:
    for i in range(len(peoples)-1):
        uf.union(peoples[i], peoples[i+1])

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
tree = [[] for _i in range(m+n+1)]
for i in range(n):
    x = list(map(int, input().split()))
    tree[i].extend([i+n for i in x[1:]])
    for j in x[1:]:
        tree[j+n].append(i)

from collections import deque
q = deque([1])
visit = [0 for _i in range(m+n+2)]
visit[1] = 1
while q:
    p = q.pop()
    for j in tree[p]:
        if visit[j]==0:
            visit[j] = 1
            q.appendleft(j)
if sum(visit[:n]) == n:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
n,m= map(int,input().split())
langdic = {key:[] for key in range(1,m+1)}
for i in range(1,n+1):
    k,*p= map(int,input().split())
    for j in p:langdic[j].append(i)
newlanglist = []
for key in langdic.keys():
    if len(langdic[key])>1:newlanglist.append((langdic[key]))
par = [-1]*(n+1)
def find(x):
    if par[x]<0:return x
    else:
        par[x]=find(par[x])
        return par[x]
def unites2(alist):
    top = min(alist)
    toproot = find(top)
    for a in alist:
        aroot = find(a)
        if top!=a:
            if aroot==toproot:pass
            else:
                grp = par[aroot]
                par[aroot]=toproot
                par[toproot]+=grp
for lis in newlanglist:unites2(lis)
c=0
for t in par[1:]:
    if t<0:c+=1
if c==1:print('YES')
else:print('NO')

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    g = [i for i in range(0,N+M+1)]
    g_num = [0] + [1 for _ in range(N)] + [0 for _ in range(M)]
    def find(x):
        if g[x] == x: return x
        g[x] = find(g[x])
        return g[x]

    def union(x,y):
        if find(x) == find(y): return
        g_num[g[x]] += g_num[g[y]]
        g_num[g[y]] = 0
        g[g[y]] = g[x]


    for i in range(1,N+1):
        for l in LI()[1:]: union(i,N+l)

    if g_num[N] == N:
        print('YES')
    else:
        print('NO')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        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())
l = [None] * n
for i in range(n):
    k, *l[i] = list(map(lambda x: int(x) - 1, input().split()))
uf = UnionFind(m)
for row in l:
    for i in range(len(row) - 1):
        uf.unite(row[i], row[i + 1])
s = set()
for row in l:
    for x in row:
        s.add(uf.find(x))
if len(s) == 1:
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
import numpy as np;from scipy.sparse import *;l=[];n,m=map(int,input().split())
for i in range(n):
  for j in input().split()[1:]:l.append((i,int(j)+n-1,1))
edge=np.array(l,dtype=np.int64).T;graph=csr_matrix(((edge[2],edge[:2])),(n+m,n+m));_,l=csgraph.connected_components(graph);print("NO"if 1 in l[:n]else"YES")

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
l=[]
for i in range(n):
    for j in input().split()[1:]:
        l.append((i,int(j)+n-1,1))
edge=np.array(l,dtype=np.int64).T
graph=csr_matrix(((edge[2],edge[:2])),(n+m,n+m))

_,ll=connected_components(graph)

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

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
tree=[[] for _ in range(N+M)]   #tree[0]~tree[N]は人の番号、tree[N+1]~tree[M]は言語に対応させる

#ここの操作は高々10^5回
for i in range(N):                      #各人について
    l=list(map(int,input().split()))
    K=l[0]
    n=len(l)
    for j in range(1,n):                #言語と人を繋ぐbidirectional treeを構成する
        tree[i].append(l[j]+N-1)
        tree[l[j]+N-1].append(i)
#print(tree)

#探査は普通のbfsで10^5回以下で終了することを利用する
d=deque()
seen=[0]*(N+M)              #木ではないので、一度見たかどうか管理。0~N番目は「人」N+1~N+M番目は「言語」
d.append(0)                 #グラフ探査の始点を入れる(何でも良い、ここでは0)
while len(d)>0:             #0(1人目)と連結な成分を探せば良い、これは1人目<=>言語x<=>...<=>i人目<=>言語m<=>j人目<=>言語n<=>...の関係を持つ、全ての言語と人の集合に相当し
                            #これに含まれる人同士が、互いにコミュニケーションを取れることになる
    v=d.popleft()
    seen[v]=1               #連結な成分に1を代入していく
    for i in tree[v]:
        if seen[i]==0:
            d.append(i)
#print(seen)
#print(seen[:N])
if sum(seen[:N])==N:        #0~N番目に全て1があれば、N人全ては互いにコミュニケーションをとれることになる
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
tree=[[] for _ in range(N+M)]

for i in range(N):
    l=list(map(int,input().split()))
    K=l[0]
    n=len(l)
    for j in range(1,n):
        tree[i].append(l[j]+N-1)
        tree[l[j]+N-1].append(i)
#print(tree)

d=deque()
seen=[0]*(N+M)
d.append(0)
while len(d)>0:
    v=d.popleft()
    seen[v]=1
    for i in tree[v]:
        if seen[i]==0:
            d.append(i)
#print(seen)
#print(seen[:N])
if sum(seen[:N])==N:
    print("YES")
else:
    print("NO")

Submission status: Accepted

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

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

    def union(self, x, y):
        x = self.root(x)
        y = self.root(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.root(x)]

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

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

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

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

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

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

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


kl = [tuple(map(int,input().split())) for i in range(n)]

for i in range(n):
    for j in range(1,kl[i][0]+1):
        uf.union(m+i,kl[i][j]-1)

for i in range(1,n):
    if not uf.is_same(m,m+i):
        print('NO')
        exit()

print('YES')

Submission status: Accepted

Solution code:
# 人も言語もグラフの頂点と見なす
# ある人がある言語を話せる場合連結となる
# 頂点のキーは[言語 or 人][番号(人番号 or 言語番号)]
# 0:言語 1:人

N,M = map(int,input().split())
from collections import defaultdict
E = [[],[]]
E[0] = [[] for i in range(M)]
E[1] = [[] for i in range(N)]

for i in range(N):
  langs = list(map(int,input().split()))[1:]
  for lang in langs:
    E[1][i].append((0,lang-1))
    E[0][lang-1].append((1,i))
    
# 任意の頂点からBFSして、全ての人の頂点が往訪済みになればOK
from collections import deque
q = deque([])
# 人で、0番目からスタート
q.append((1,0))
seen = [[],[]]
seen[0] = [False for i in range(M)]
seen[1] = [False for i in range(N)]

while q:
  kind,v = q.popleft()
  if seen[kind][v]:
    continue
  seen[kind][v] = True
  children = E[kind][v]
  for child in children:
    q.append([child[0],child[1]])
    
for s in seen[1]:
  if not s:
    print("NO")
    break
else:
  print("YES")

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**9)

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

def dfs(num):
    visited[num]=1
    for item in way[num]:
        if visited[item]==0:
            dfs(item)
    return 

mem=[-1]*M
way=[[] for i in range(N)]
visited=[0]*N
for n in range(N):
    temp=list(map(int,input().split()))
    
    for i in range(temp[0]):
        if mem[temp[i+1]-1]==-1:
            mem[temp[i+1]-1]=n
        else:
            way[mem[temp[i+1]-1]].append(n)
            way[n].append(mem[temp[i+1]-1])

for i in range(N):
    way[i]=list(set(way[i]))

dfs(0)

if visited.count(0)==0:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
import collections
d=collections.defaultdict(int)
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(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 same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
uf=unionfind(n)
for i in range(1,n+1):
    l=list(map(int,input().split()))
    for j in l[1:]:
        if d[j]==0:
            d[j]=i
        else:
            uf.unite(d[j],i)
if uf.count(1)==n:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
graph=[[] for i in range(n+m)]
for i in range(n):
    l=list(map(int,input().split()))
    for j in range(1,l[0]+1):
        graph[n-1+l[j]].append(i)
        graph[i].append(n-1+l[j])
visited=[False]*(n+m)
Q=deque([0])
while Q:
    v=Q.popleft()
    for i in graph[v]:
        if visited[i]:continue
        Q.append(i)
        visited[i]=True
if False in visited[:n]:print("NO")
else:print("YES")

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import queue
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


class UF:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
    
    def get_parent(self, a):
        p = self.parent[a]
        if a == p:
            return a
        
        q = self.get_parent(p)
        self.parent[a] = q
        return q

    def make_pair(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa == pb:
            return
        
        self.parent[pa] = pb
        self.parent[a] = pb
    
    def is_pair(self, a, b):
        return self.get_parent(a) == self.get_parent(b)


def main():
    N, M = read_values()
    uf = UF(N + M)
    for i in range(N):
        L = read_list()
        for l in L[1:]:
            uf.make_pair(i, l - 1 + N)

    for n in range(1, N):
        if not uf.is_pair(0, n):         
            print("NO")
            return
    print("YES")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int, input().split( ))
p= [i for i in range(n)]+[n+j for j in range(m)]
rk = [0]*(n+m)
def rt(a):
    if a==p[a]:
        return a
    p[a] = rt(p[a])
    return p[a]
def uni(a,b):
    ra = rt(a);rb=rt(b)
    if ra==rb:
        return
    if rk[ra]>rk[rb]:
        p[rb] = ra
    else:
        if rk[ra]==rk[rb]:
            p[ra] = rb
            rk[rb]+=1
        else:
            p[ra]=rb 
    return

kl = {}
for i in range(n):
    ki,*li, = map(int, input().split( ))
    kl[i] = li
for ki in kl:
    for j in range(len(kl[ki])):
        kl[ki][j]-=1

for ki in kl:
    for lij in kl[ki]:
        uni(ki,lij+n)
for i in range(n):
    rt(i)
if len(set(p[:n]))==1:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        self.p = [-1] * n
        self.rank = [1]*n
    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[y] += 1
            self.p[x] = y
            return True
        else:
            return False

    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):
    kl = list(map(int,input().split()))
    k,L = kl[0],kl[1:]
    for l in L:
        uf.unite(i,l+n-1)
p = uf.find(0)
ans = 'YES'
for i in range(1,n):
    if p != uf.find(i):
        ans = 'NO'
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
lanper=[-1]*m
uf=UnionFind(n)
for i in range(n):
    for j in list(map(int,input().split()))[1:]:
        if lanper[j-1]==-1:lanper[j-1]=i
        else:uf.unite(lanper[j-1],i)
print("YES") if uf.connected() else print("NO")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)
lanper=[-1]*m
uf=UnionFind(n)
for i in range(n):
    for j in list(map(int,input().split()))[1:]:
        if lanper[j-1]==-1:lanper[j-1]=i
        else:uf.unite(lanper[j-1],i)
print("YES") if uf.size(0)==n else print("NO")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)
lanper=[-1]*m
uf=UnionFind(n)
for i in range(n):
    for j in list(map(int,input().split()))[1:]:
        if lanper[j-1]==-1:lanper[j-1]=i
        else:uf.unite(lanper[j-1],i)
print("YES") if uf.group_count()==1 else print("NO")

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

import collections
import itertools
import operator


class UnionFind:
    def __init__(self, x):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)
        self.size = collections.defaultdict(lambda: 1)
        if x is not None:
            for elem in range(x+1):
                _, _, _ = self.parent[elem], self.rank[elem],self.size[elem]

    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 not self.are_same(x,y):
            xx = self.size[x]
            yy = self.size[y]
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += xx
            else:
                self.parent[y] = x
                self.size[x] += yy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def are_same(self, x, y):
        '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))'''
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]

N,M = m()

uf = UnionFind(N-1)

fa = [-1 for i in range(M)]

for i in range(N):
    a = l()

    for j in range(a[0]):
        j += 1
        if fa[a[j]-1] == -1:
            fa[a[j]-1] = i
        else:
            uf.unite(fa[a[j]-1],i)

po = list(uf.grouper())

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