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: Wrong Answer

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._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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
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[j].append(i)
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: Wrong Answer

Solution code:
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
  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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  
N,M = map(int, input().split())
u = UnionFind(N+M)
for i in range(N):
  inf = list(map(int, input().split()))
  for l in inf[1:]:
    u.unit(i,N+l-1)

ans = all(u.same(i,i+1) for i in range(N-1))
if ans:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

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

n, m = map(int, input().split())
g = [[] for _ in range(n)]
d = {}
for i in range(n):
    kl = list(map(int, input().split()))
    L = kl[1:]
    L = [l-1 for l in L]
    for l in L:
        if l not in d:
            d[l] = i
        else:
            g[d[l]].append(i)

from collections import deque
s = deque()
s.append(0)
visit = [-1]*n
visit[0] = 0
while s:
    x = s.pop()
    for nx in g[x]:
        if visit[nx] == -1:
            visit[nx] = 0
            s.append(nx)
if min(visit) != -1:
    print('YES')
else:
    print('NO')

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
setrecursionlimit(2000)
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [i for i in range(n)]
        # rank
        self.rank = [0] * n
        self.size = [1] * n

    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 check(self, x, y):
        # x,yが同じ集合に属するかどうか調べる
        return self.find(x) == self.find(y)


    #どちらに併合するか決める
    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        # rankの小さいものを大きいほうにくっつける
        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]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
n,m=map(int,input().split())
lan=[]
for i in range(n):
    k=list(map(int,input().split()))
    lan.append(set(k[1:]))
#print(lan)
uf=UnionFind(n)

for i in range(n):
    for j in range(n):
        if i==j:continue
        if lan[i]&lan[j]:
            uf.par[j]=uf.par[i]

for i in range(n):
    uf.find(i)
#print(uf.par)
print('YES' if len(set(uf.par))==1 else 'NO')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
lan=[]
for i in range(n):
    k=list(map(int,input().split()))
    lan.append(set(k[1:]))
#print(lan)
languages=lan[0]
for i in range(1,n):
    if not languages&lan[i]:
        print('NO')
        exit()
    languages=languages|lan[i]
print('YES')

Submission status: Wrong Answer

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

# ユニオンファインド
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

y=uf.group_count()
if y==1:
    print('YES')
    exit()
else:
    count=0
    z=list(uf.all_group_members().values())
    for i in range(y):
        if len(z[i])>=2:
            count+=1
            if count>=2:
                print('NO')
                exit()
        else:
            if x[z[i][0]] == n:
                print('YES')
                exit()

            elif x[z[i][0]]>0:
                print('NO')
                exit()
    print('YES')

Submission status: Wrong Answer

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

# ユニオンファインド
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

n,m= map(int, input().split())
a= [list(map(int, input().split())) for i in range(n)]
uf=UnionFind(m)
x=[0]*m
for i in range(n):
    if a[i][0]==1:
        x[a[i][1]-1]=+1
    else:
        for j in range(1,len(a[i])-1):
            uf.union(a[i][j]-1,a[i][j+1]-1)
    print(i)
y=uf.group_count()
if y==1:
    print('YES')
    exit()
else:
    count=0
    z=list(uf.all_group_members().values())
    for i in range(y):
        if len(z[i])>=2:
            count+=1
            if count>=2:
                print('NO')
                exit()
        else:
            if x[z[i][0]] == n:
                print('YES')
                exit()
                
            elif x[z[i][0]]>0:
                print('NO')
                exit()
    print('YES')

Submission status: Wrong Answer

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

# ユニオンファインド
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

# ユニオンファインド
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

if y==1:
    print('YES')
    exit()
else:
    count=0
    z=list(uf.all_group_members().values())
    for i in range(y):
        if len(z[i])>=2:
            count+=1
            if count>=2:
                print('NO')
                exit()
        else:
            if x[z[i][0]]==1:
                print('NO')
                exit()
    print('YES')

Submission status: Wrong Answer

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

# ユニオンファインド
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

n,m= map(int, input().split())
a= [list(map(int, input().split())) for i in range(n)]
uf=UnionFind(m)
x=[0]*m
for i in range(n):
    if len(a[i])==2:
        x[a[i][1]-1]=1
    else:
        for j in range(1,len(a[i])-1):
            uf.union(a[i][j]-1,a[i][j+1]-1)
y=uf.group_count()
if y==1:
    print('YES')
    exit()
else:
    count=0
    z=list(uf.all_group_members().values())
    for i in range(y):
        if len(z[i])>=2:
            count+=1
            if count>=2:
                print('NO')
                exit()
            else:
                if x[z[i][0]]==1:
                    print('NO')
                    exit()
    print('YES')

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:


#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root

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

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

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

    print("YES")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
import itertools

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

N, M = rl()
L = [rl() for _ in range(N)]
translate = [set() for _ in range(M+1)] # 0は使わない
for i, x in enumerate(L):
    k, *language = x
#    s = set(language)
    for l in language:
        translate[l].add(i)

for x, y in itertools.combinations(range(N), 2):
    x_use_language = set(L[x][1:])
    y_use_language = set(L[y][1:])
    x_can_speak = set([x])
    y_can_speak = set([y])
    for xuse in x_use_language:
        x_can_speak = x_can_speak.union(translate[xuse])
    for yuse in y_use_language:
        y_can_speak = y_can_speak.union(translate[yuse])
    
    if len(x_can_speak & y_can_speak) == 0:
        print('NO')
        exit()

print('YES')
# 26

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def bfs(s, n, graph):
    que = deque([])
    flag = [False for _ in range(n)]
    flag[s] = True
    for i in range(len(graph[s])):
        if flag[graph[s][i]]:
            continue
        que.append(graph[s][i])
        flag[graph[s][i]] = True
    while que:
        to = que.pop()
        for i in range(len(graph[to])):
            if flag[graph[to][i]]:
                continue
            flag[graph[to][i]] = True
    print(s,flag)
    for i in range(n):
        if not flag[i]:
            print('NO')
            return
                
def main():
    n,m = inpm()
    kl = []
    root = [[] for _ in range(m)]
    for j in range(n):
        k = inpl()
        kl.append(tuple(k))
        for i in range(1,k[0]+1):
            root[k[i]-1].append(j)
    graph = [[] for _ in range(n)]
    for i in range(m):
        for comb in combinations(root[i],2):
            x = comb[0]
            y = comb[1]
            graph[x].append(y)
            graph[y].append(x)
    for p in range(n):
        s = p
        que = deque([])
        flag = [False for _ in range(n)]
        flag[s] = True
        for i in range(len(graph[s])):
            if flag[graph[s][i]]:
                continue
            que.append(graph[s][i])
            flag[graph[s][i]] = True
        while que:
            to = que.pop()
            for i in range(len(graph[to])):
                if flag[graph[to][i]]:
                    continue
                flag[graph[to][i]] = True
        for i in range(n):
            if not flag[i]:
                print('NO')
                return
    print('YES')
    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#C-Interpretation
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())
uni=UnionFind(n)
langulist=[[] for i in range(m+1)]
for i in range(1,n+1):
    lists=list(map(int,input().split()))
    use=lists[1:]
    for j in range(len(use)):
        langulist[use[j]].append(i)
uni=UnionFind(n)
for some in langulist:
    if len(some)<=1:
        pass
    else:
        first=some[0]
        for i in range(1,len(some)):
            uni.union(first,some[i])
a=uni.par
del a[0]
flags=True
for i in range(n):
  if a[0]!=a[i]:
    flags=False
if flags:
  print("YES")
else:
  print("NO")

Submission status: Wrong Answer

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)
#C-Interpretation
n,m=map(int,input().split())
uni=UnionFind(n)
langulist=[[] for i in range(m+1)]
for i in range(1,n+1):
    lists=list(map(int,input().split()))
    use=lists[1:]
    for j in range(len(use)):
        langulist[use[j]].append(i)
for some in langulist:
    if not some:
        pass
    elif some:
        first=some[0]
        for what in some:
            uni.union(first,what)
            uni.find(first)
            uni.find(what)
Ans=uni.par
del Ans[0]
answer=len(set(Ans))
if answer==1:
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, L):
    g = defaultdict(set)
    for l in L:
        for i, j in combinations(l, r=2):
            g[i].add(j)
            g[j].add(i)
    rem = set(range(1, N+1))
    for i in range(1, N+1):
        r = set([i])
        for j in g[i]:
            r.add(j)
        for j in list(r):
            for k in g[j]:
                r.add(k)
    rem = rem - r

    return 'YES' if len(rem) == 0 else 'NO'


def main():
    N, M = read_int_n()
    L = [read_int_n()[1:] for _ in range(N)]
    print(slv(N, M, L))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, L):
    g = defaultdict(list)
    for l in L:
        for i, j in combinations(l, r=2):
            g[i].append(j)
            g[j].append(i)
    rem = set(range(1, N+1))
    for i in range(1, N+1):
        r = set([i])
        for j in g[i]:
            r.add(j)
        for j in list(r):
            for k in g[j]:
                r.add(k)
    rem = rem - r

    return 'YES' if len(rem) == 0 else 'NO'


def main():
    N, M = read_int_n()
    L = [read_int_n()[1:] for _ in range(N)]
    print(slv(N, M, L))


if __name__ == '__main__':
    main()