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:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# Union-Find木
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)
        # あるノードを根とする集合に属するノード数
        self.size = [1] * (n+1)
        # あるノードを根とする集合が木かどうか
        self.tree = [True] * (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 x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # あるノードの属する集合のノード数
    def get_size(self, x):
        return self.size[self.find(x)]

    # 木かどうかの判定
    def is_tree(self, x):
        return self.tree[self.find(x)]

N,M=MAP()

lang=[[] for i in range(M+1)]
for i in range(N):
    for j in LIST()[1:]:
        lang[j].append(i+1)

uf=UnionFind(N)
for i in range(1, M+1):
    for j in range(1, len(lang[i])):
        a,b=lang[i][j-1],lang[i][j]
        if not uf.same(a, b):
            uf.union(a, b)

root=uf.find(1)
for i in range(2, N+1):
    if uf.find(i)!=root:
        NO()
        exit()
YES()

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def bfs(path, start, visited_set):
    que = deque([start])
    while 1:
        if len(que) == 0:
            break;
        nd = que.popleft()
        for adj in path[nd]:
            if adj not in visited_set:
                visited_set.add(adj)
                que.append(adj)



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    path = {}
    ofset = 1000000
    for i in range(N):
        path[i + ofset] = []

    for i in range(N):
        input_raw = read_func().strip().split()
        K = int(input_raw[0])
        for j in range(1, K + 1):
            path[i + ofset].append(int(input_raw[j]))
            if int(input_raw[j]) not in path:
                path[int(input_raw[j])] = [i + ofset]
            else:
                path[int(input_raw[j])].append(i + ofset)
    visited_set = set([])
    bfs(path, ofset, visited_set)
    for i in range(N):
        if i + ofset not in visited_set:
            print "NO"
            return
    print "YES"

if __name__ == '__main__':
    main()

Submission status: Accepted

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

UF = list(range(M + 1))


def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    a[x] = a[y] = min(x, y)


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


for kl in KL:
    K, L = kl[0], kl[1:]
    for i in range(K - 1):
        unite(UF, L[i], L[i + 1])
for kl in KL:
    if not same(UF, KL[0][1], kl[1]):
        print('NO')
        exit()
print('YES')

Submission status: Accepted

Solution code:
input = __import__('sys').stdin.readline
MIS = lambda: map(int,input().split())

n, m = MIS()
adj = [[] for i in range(n+1)]
speaker = [[] for i in range(m+1)]
for i in range(n):
    lang = list(MIS())[1:]
    for x in lang: speaker[x].append(i+1)
for L in speaker:
    for i in range(len(L)-1):
        adj[L[i]].append(L[i+1])
        adj[L[i+1]].append(L[i])

vis = [False]*(n+1); vis[1] = True
stack = [1]
while stack:
    p = stack.pop()
    for q in adj[p]:
        if vis[q]: continue
        vis[q] = True; stack.append(q)
print("YES" if sum(vis) == n else "NO")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

n,m=map(int,input().split())
f=lambda x:int(x)-1

langs=[[] for _ in range(m)]
speakers=[[] for _ in range(n)]
used_langs=[False]*m
used_speakers=[False]*n

for i in range(n):
  *l,=map(f,input().split()[1:])
  speakers[i].extend(l)
  for j in l:
    langs[j].append(i)

def dfs(n):
  if used_speakers[n]:
    return
  used_speakers[n]=True
  for i in speakers[n]:
    if used_langs[i]:continue
    used_langs[i]=True
    for j in langs[i]:
      dfs(j)

dfs(0)
if not False in used_speakers:
  print("YES")
else:
  print("NO")

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
g = [[] for i in xrange(m)]
for i in xrange(n):
    ipt = map(int, raw_input().split())
    k = ipt[0]
    for e in ipt[1:]:
        g[e-1].append(i)
parent = range(n)
def root(x):
    if x == parent[x]:
        return x
    parent[x] = root(parent[x])
    return parent[x]
def unite(x, y):
    px = root(x)
    py = root(y)
    if px < py:
        parent[py] = px
    elif px > py:
        parent[px] = py
    return min(px, py)
for e in g:
    for i in xrange(len(e)-1):
        unite(e[i], e[i+1])
for i in xrange(n):
    root(i)
print "YES"*(sum(parent) == 0) or "NO"

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    N, M = [int(i) for i in input().split()]
    L = [[] for _ in range(M+1)]
    for i in range(N):
        for j in map(int, input().split()[1:]):
            L[j].append(i)
    uf = UnionFind()
    for i, l in enumerate(L):
        #print("Lang {}".format(i))
        if not l:
            continue
        a = l[0]
        for b in l[1:]:
            #print(a, b)
            uf.union(a, b)
    # print(uf.table)
    print("YES" if uf.size(0) == N else "NO")
    

class UnionFind(object):

    def __init__(self):
        self.table = defaultdict(lambda: -1)

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

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

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

(N, M) = reads()

d = defaultdict(list)
V = set()

for i in range(N):
  V.add(("p", i+1))
for j in range(M):
  V.add(("l", j+1))

for i in range(1, N+1):
  Ls = reads()[1:]
  for j in Ls:
    d[("l", j)].append(("p", i))
    d[("p", i)].append(("l", j))

def walk(v):
  V.discard(v)
  for w in d[v]:
    if w in V:
      walk(w)

# for (k, v) in d.items():
#   print(k, v)

v = ("p", 1)
walk(v)

# print(V)

print("NO" if len([v for v in V if v[0] == "p"]) > 0 else "YES")

Submission status: Accepted

Solution code:
# coding: utf-8

import collections
import sys
sys.setrecursionlimit(100000)

def dfs(i):
    if visited[i] == 1:
        return
    visited[i] = 1
    for j in speakers[i]:
        if used_lang[j] == 1:
            continue
        used_lang[j] = 1
        for k in langs[j]:
            dfs(k)


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

langs = collections.defaultdict(list)
speakers = [[] for _ in range(N)]

for i in range(N):
    ls = list(map(int, input().split()))
    for j in range(1, ls[0] + 1):
        langs[ls[j]-1].append(i)
        speakers[i].append(ls[j]-1)

visited = [0] * N
used_lang = [0] * M
dfs(0)

if 0 not in visited:
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)

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

#n,m<=10**5

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)

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

#n,m<=10**5

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:
        lastcheck.add(kl[0])
    else:
        for item in kl[1:]:
            uf.union(kl[0]-1,item-1)
    klkl.append(kl)
uf_list=uf.members(item-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")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)

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

#n,m<=10**5

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:
        lastcheck.add(kl[0])
    else:
        for item in kl[1:]:
            uf.union(kl[0]-1,item-1)
    klkl.append(kl)
uf_list=uf.members(item-1)    

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

Submission status: Runtime Error

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

#n,m<=10**5

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:
        lastcheck.add(kl[0])
    else:
        for item in kl[1:]:
            uf.union(kl[0]-1,item-1)
    klkl.append(kl)
uf_list=uf.members(item-1)    

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

Submission status: Runtime Error

Solution code:
4 6
3 1 2 3
2 4 2
2 4 6
1 6

Submission status: Runtime Error

Solution code:
from scipy.sparse import*
(n,m),*t=[map(int,t.split())for t in open(0)]
*b,a=zip(*[(i,j+n,1)for i,(_,*t)in enumerate(t)for j in t])
print('YNEOS'[1in csgraph.connected_components(csr_matrix((a,b),[n*m]*2))[1][:n]::2])

Submission status: Runtime Error

Solution code:
from scipy.sparse import*
(n,m),*t=[map(int,t.split())for t in open(0)]
*b,a=zip(*[(i,j+n,1)for i,(_,*t)in enumerate(t)for j in t])
print('YNEOS'[1in csgraph.connected_components(csr_matrix((a,b),[n*9]*2))[1][:n]::2])

Submission status: Runtime Error

Solution code:
from scipy.sparse import*
(n,m),*t=[map(int,t.split())for t in open(0)]
*b,a=zip(*[(i,j+n,1)for i,(_,*t)in enumerate(t)for j in t])
print('YNEOS'[1in csgraph.connected_components(csr_matrix((a,b),[m*9]*2))[1][:n]::2])

Submission status: Runtime Error

Solution code:
from scipy.sparse import*
(n,m),*t=[map(int,t.split())for t in open(0)]
*b,a=zip(*[(i,j+n,1)for i,(_,*t)in enumerate(t)for j in t])
print('YNEOS'[1in csgraph.connected_components(csr_matrix((a,b),[m*3]*2))[1][:n]::2])

Submission status: Runtime Error

Solution code:
from scipy.sparse import*
(n,m),*t=[map(int,t.split())for t in open(0)]
*b,a=zip(*[(i,j+n,1)for i,(_,*t)in enumerate(t)for j in t])
print('YNEOS'[1in csgraph.connected_components(csr_matrix((a,b),[n*3]*2))[1][:n]::2])

Submission status: Runtime Error

Solution code:
from scipy.sparse import*;(n,m),*t=[map(int,t.split())for t in open(0)];*b,a=zip(*[(i,j+n-1,1)for i,(_,*t)in enumerate(t)for j in t]);print("YNEOS"[1in csgraph.connected_components(csr_matrix(((a,t)),[n+m]*2))[1][:n]::2])

Submission status: Runtime Error

Solution code:
from numpy import*;from scipy.sparse import*;(n,m),*p=[map(int,o.split())for o in open(0)];e,*f=array([(i,j+n-1,1)for i,q in enumerate(p)for j in list(q)[1:]]).T[:3];print("YNEOS"[1in csgraph.connected_components(csr_matrix(((f,e)),[n+m]*2))[1][:n]::2])

Submission status: Runtime Error

Solution code:
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: Runtime Error

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[ra]+=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: Runtime Error

Solution code:
N,M=map(int,input().split())
D=[set() for i in range(M)]#i番目の言語を話せる人
L=[set() for i in range(N)]#i番目の人が話せる言語
for i in range(N):
    Li=list(map(int,input().split()))[1:]
    for l in Li:
        L[i].add(l-1)
        D[l-1].add(i)
seen=[False for i in range(N)]
seen[0]=True
def dfs(i):
    for l in L[i]:
        for k in D[l]:
            if not seen[k]:
                seen[k]=True
                dfs(k)

dfs(0)

if all(seen):
    print('YES')
else:
    print('NO')

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
adjacent_list = [[] for i in range(n+1+m+1)]
for i in range(1,n+1):
    for j in list(map(int, input().split()))[1:]:
        adjacent_list[i].append(j)
        adjacent_list[i].append(j)
finished = set()
def dfs(node):
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
dfs(1)
flag = True
for i in range(1,n+1):
    if i not in finished:
        flag = False
if flag:
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

Solution code:
class unionFind:
    parent = []

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

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

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

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

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

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("YES")  # type: str


def no():
    print("NO")  # type: str


class Graph(object):

    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


class UnionFind(object):

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

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

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

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


def main():

    N, M = map(int, input().split())
    L = [0]*N
    for i in range(N):
        L[i] = list(map(int, input().split()))

    # 前Nは人、後ろMは言語
    uf = UnionFind(N+M)

    for i in range(N):
        for l in L[i]:
            # 人iは言語L[i]と同じグループ
            uf.unite(i, N+l)

    # 人はすべて同じグループであるか
    flag = True
    for i in range(N):
        if not uf.same(0, i):
            flag = False
            break
    if flag:
        yes()
    else:
        no()

    pass


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

#人は0からN-1,言語は1からMまで
N, M = rl()
KL = [rl() for _ in range(N)]
speak_lan = [[] for _ in range(M+1)] #0は使わない
for i, x in enumerate(KL):
    k, *lan = x
    for l in lan:
        speak_lan[l].append(i)

communicate = set()

def dfs(person):
    global communicate
    lan = KL[person][1:]
    for l in lan:
        for p in speak_lan[l]:
            if p not in communicate:
                communicate.add(p)
                dfs(p)

dfs(0)
if len(communicate) == N:
    print('YES')
else:
    print('NO')

Submission status: Runtime Error

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


def main():
    N = int(input())
    ans = set()
    for i in range(1, N):
        ans.add(i)
        if sum(ans) >= N:
            break
    m = sum(ans) - N
    if m in ans:
        ans.remove(m)
    for i in ans:
        print(i)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix


def main():
    n, m = map(int, sys.stdin.readline().split())
    can_speak = [[] for _ in range(m + 1)]
    for i in range(n):
        *languages, = map(int, sys.stdin.readline().split())
        for l in languages[1:]:
            can_speak[l].append(i)
    
    G = np.zeros((n, n), np.int64)

    for language in can_speak:
        for j in range(len(language) - 1):
            G[language[j]][language[j+1]] = 1
            G[language[j+1]][language[j]] = 1

    shortest_path = dijkstra(csgraph=csr_matrix(G), directed=False, indices=0)

    if np.any(shortest_path == np.inf):
        ans = 'NO'
    else:
        ans = 'YES'
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

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

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

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

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

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


N, M = map(int, input().split())
Un = UnionFind(M)
D = defaultdict(lambda: [])
for i in range(N):
    _, *L = map(int, input().split())
    for l in L:
        D[l-1].append(i)
for i in range(M):
    if len(D[i]) > 1:
        t = D[i]
        for d in t[1:]:
            Un.union(t[0], d)
if Un.size[Un.find(0)] == N:
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

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

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

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

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

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


N, M = map(int, input().split())
Un = UnionFind(M)
D = defaultdict(lambda: [])
for i in range(N):
    _, *L = map(int, input().split())
    for l in L:
        D[l].append(i)
for i in range(M):
    if len(D[i]) > 1:
        t = D[i]
        for d in t[1:]:
            Un.union(t[0], d)
if Un.size[Un.find(0)] == N-1:
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

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

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

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

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

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


N, M = map(int, input().split())
Un = UnionFind(M)
D = defaultdict(lambda: set())
for i in range(N):
    _, *L = map(int, input().split())
    for l in L:
        D[l].add(i)
for i in range(M):
    l = list(D[i])
    for d in l[1:]:
        Un.union(l[0], d)
if Un.size[Un.find(0)] == N-1:
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

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

    def ans(self):
        print(len(set(self.par))-1)

n,m=map(int,input().split())
uf=UnionFind(n)
l=[[] for i in range(m)]
for i in range(n):
    k=list(map(int,input.split()))
    k=[1:]
    for j in k:
        l[j-1].append(i)
    
for i in range(m):
    if len(l[i])>0:
        ll=l[i][0]
        for j in range(len(l[i])-1):
            uf.union(ll,l[i][j+1])

for i in range(1,n+1):
    uf.find(i)

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

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
L = []
for i in range(N):
  tmp = list(map(int,input().split()))
  L.append(tmp[1:])
#print(L)

# 人(0~N-1)と言語(N~M-1)の間で二部グラフを作る
E = [set() for _ in range(N+M)]
for i in range(N):
  for l in L[i]:
    E[i].add(l+N-1)
    E[l+N-1].add(i)
#print(E)

# 人のノードすべてに到達可能であればYES
Visited = [0 for _ in range(N+M)]
def dfs(v):
  Visited[v] = 1
  for u in E[v]:
    if Visited[u] == 0:
      dfs(u)
dfs(0)
print('YES' if sum(Visited[:N]) == N else 'NO')