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:
# -*- 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()
        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:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


def main():
    n, m = map(int, input().split())

    for i in range(n):
        l = list(map(int, input().split()))
        if i != 0:
            f = False
            for j in range(l[0]):
                if c[l[j + 1]] > 0:
                    f = True
                    break
            
            if not f:
                print("NO")
                exit()
    
        c = Counter(l[1:])

    print("YES")
    

        
        
        
            

    
   


if __name__ == '__main__':
    main()

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)

    def ans(self):
        return (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=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: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 併合
    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
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

n,m=map(int,input().split())
kl=[list(map(int,input().split())) for i in range(n)]
uf=UnionFind(m)
for i in range(n):
    for j in range(2,kl[i][0]+1):    
        uf.union(kl[i][1], kl[i][j])

flag=uf.par[1]
for i in range(2,n):
    if flag!=uf.par[kl[i][1]]:
        print("NO")
        quit()
print("YES")

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
L = [set(list(map(int,input().split()))[1:]) for _ in range(N)]

s = L[0]
check = [0] * N

for _ in range(2):
    for i in range(N):
        if s & L[i]:
            check[i] = 1
            s |= L[i]

if all(check):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
L = [set(list(map(int,input().split()))[1:]) for _ in range(N)]

s = set()
s.update(L[0])
check = [0] * N

for _ in range(2):
    for i in range(N):
        if s & L[i]:
            check[i] = 1
            s.update(L[i])

if all(check):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

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

l=[]
for i in range(n):
    t=(list(map(int,input().split())))
    l.append(set(t[1:]))
#print(l)
if n==2:
    if l[0]&l[1]:
        print('YES')
    else:
        print('NO')
else:
    lll=[]
    for i in range(n):
        ll={}
        for j in range(i+1,n):
            if set(l[i])&set(l[j]):
                ll=set(ll)|set(l[i])|set(l[j])
        lll.append(ll)
    lll=lll[:-1]
    #print(lll)
    l_l={}
    for i in range(n-1):
        for j in range(i+1,n-1):
            if set(l[i])&set(l[j]):
                l_l=set(l_l)|set(l[i])|set(l[j])
    #print(l_l)
    count=0
    for i in range(n):
        if l[i]&l_l:
            count+=1
    if count==n:
        print('YES')
    else:
        print('NO')

Submission status: Wrong Answer

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

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)

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

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


N, M = map(int, input().split())
uf = UnionFind(M + 1)
used = set()
for _ in range(N):
    K, *L = map(int, input().split())
    for l in L:
        uf.union(L[0], l)
    used.update(L)

if uf.size(1) == len(used):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
from collections import deque

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

es_lang = [[] for _ in range(M+1)] # 各言語の番号がidxで、それを話せる人が中身
es_p = [[] for _ in range(N+1)] # 各人の番号がidxで、その人の話せる言語が中身
for i in range(N):
    KL = list(map(int, input().split()))
    es_p[i+1].extend(KL[1:])
    for j in KL[1:]:
        es_lang[j].append(i+1)

checked_lang = [False] * (M+1)
checked_p = [False] * (N+1)

#人１からスタートする
stack_p = [1]
checked_p[1] = True
while len(stack_p) > 0:
    for p in stack_p:
        #p = stack_p.pop() # 調べる人を取り出す
        checked_p[p] = True
        stack_lang = []
        for lang in es_p[p]: #人ｐが話せる言語について調べる
            if checked_lang[lang] == False: # まだその言語を調査してないとき
                stack_lang.append(lang)
                checked_lang[lang] = True

        # 人pの持つ言語をだれが話せるか調べる
        new_stack_p = []
        for lang in stack_lang:
            for pp in es_lang[lang]:
                if checked_p[pp] == False:
                    new_stack_p.append(pp)
                    checked_p[pp] = True

    if all(checked_p[1:]):
        print("YES")
        exit()
    if len(new_stack_p) > 0:
        stack_p = new_stack_p
    else:
        break


print("NO")

Submission status: Wrong Answer

Solution code:
from collections import deque

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

es_lang = [[] for _ in range(M+1)] # 各言語の番号がidxで、それを話せる人が中身
es_p = [[] for _ in range(N+1)] # 各人の番号がidxで、その人の話せる言語が中身
for i in range(N):
    KL = list(map(int, input().split()))
    es_p[i+1].extend(KL[1:])
    for j in KL[1:]:
        es_lang[j].append(i+1)

checked_lang = [False] * (M+1)
checked_p = [False] * (N+1)

#人１からスタートする
stack_p = [1]
checked_p[1] = True
while len(stack_p) > 0:
    for p in stack_p:
        stack_lang = []
        for lang in es_p[p]: #人ｐが話せる言語について調べる
            if checked_lang[lang] == False: # まだその言語を調査してないとき
                stack_lang.append(lang)
                checked_lang[lang] = True

        # 人pの持つ言語をだれが話せるか調べる
        new_stack_p = []
        for lang in stack_lang:
            for pp in es_lang[lang]:
                if checked_p[pp] == False:
                    new_stack_p.append(pp)
                    checked_p[pp] = True

    if all(checked_p[1:]):
        print("YES")
        exit()
    if len(new_stack_p) > 0:
        stack_p = new_stack_p
    else:
        break


print("NO")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#CODEFESTIVAL2016Final C

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def union(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

n,m = LI()
par = [i for i in range(n)]
rank = [0]*n
language = [[] for _ in range(m)]
for i in range(n):
    a = LI()
    k = a[0]
    for j in range(1,k+1):
        language[a[j]-1].append(i)
for i in range(m):
    l = len(language[i])
    for j in range(l-1):
        if root(language[i][j]) != root(language[i][j+1]):
                union(language[i][j],language[i][j+1])
for i in range(n-1):
    if par[i] != par[i+1]:
        print('NO')
        quit()
print('YES')

Submission status: Wrong Answer

Solution code:
def bfs(graph,pp,n):
    stk = [n]
    seen = set()
    seenp = set()
    for _ in range(2):
        next = []
        while(stk):
            q = stk.pop()
            if(q in seen):continue
            seen.add(q)
            seenp |= pp[q]
            next+=list(graph[q])
        stk = next
    return seenp
#%%
N,M = [int(x) for x in input().split()]
people = [[i]+[int(x) for x in input().split()]for i in range(N)]
#%%
gp = [set() for _ in range(M)]
pp = [set() for _ in range(M)]
ns = set()
for p in people:
    num=p[0]
    L=p[2:]
    for l in L:
        pp[l-1].add(num)
        ns.add(l-1)
        for l2 in L:
            if(l==l2):continue
            gp[l-1].add(l2-1)
            gp[l2-1].add(l-1)

for i in ns:
    x = bfs(gp,pp,i)
    if(len(x)==N):
        print('YES')
        break
else:
    print('NO')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
N,M = map(int,input().split())
R = [[] for _ in range(N+M)]
for i in range(N):
    L = list(map(lambda x:int(x)-1+N,input().split()))[1:]
    R[i]+=L
    for l in L:
        R[l].append(i)
A = [0]*(N+M)
def f(v):
    global R,A
    A[v] = 1
    for c in R[v]:
        if c<N and A[c]==1: continue
        f(c)
f(0)
print("YES" if sum(L[:N])==N else "NO")

Submission status: Wrong Answer

Solution code:
print("YES")

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M = map(int,input().split())
edge = [[]for i in range(N+M)]
for i in range(N):
    l = list(map(int,input().split()))[1:]
    for j in l:
        edge[i].append(j-1)
        edge[N+j-1].append(i)
A = [0]*(N+M)
A[0] = 1
queue = deque([0])
while queue != deque([]):
    p = queue.popleft()
    for i in edge[p]:
        if A[i] == 0:
            A[i] = 1
            queue.append(i)

if sum(A[:N]) == N:
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
import heapq
N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N]

E = [{} for _ in [0]*(N+M)]
for i,kl in enumerate(KL):
    for l in kl[1:]:
        E[i][N+l-1] = 1
        E[N+l-1][i] = 1

def Dijkstra(N,E,start):
    d = [-1]*N
    q = [(0,start-1)]
    while q:
        ci,i = heapq.heappop(q)
        if d[i]!= -1:continue
        d[i] = ci
        for j,cj in E[i].items():
            if d[j]!=-1:continue
            heapq.heappush(q,(ci+cj,j))
    return d

d = Dijkstra(N+M,E,0)
ans = d[:N].count(-1)==0
print("YES" if ans else "NO")

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N]

E = [[] for _ in [0]*(N+M)]
for i,kl in enumerate(KL):
    for l in kl[1:]:
        E[i].append(N+l-1)
        E[N+l-1].append(i)

start = 0
d = [-1]*(N+M) #d[0] - d[N-1]:人, d[N] - D[N+M-1]:言語
d[start] = 0
q = [start]
while q:
    i = q.pop()
    for j in E[i]:
        if d[j]==-1:continue
        d[j] = d[i]+1
        q.append(j)

ans = True
for b in d[:N]:
    ans = ans and (b>=0)
print("YES" if ans else "NO")

Submission status: Wrong Answer

Solution code:
class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            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:
            # 高い方をxとする。
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            # 同じ高さの時は高さ+1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える
            self.par[x] += self.par[y]
            self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]


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


# l[i] 言語iを話す人のリスト
l = [[]for i in range(m)]
for i in range(n):
    for j in range(1,k[i][0]+1):
        l[k[i][j]-1].append(i)

# a[i] 人iと会話が成立する人のset
a = [set() for i in range(n)]
for i in range(n):
    for j in range(1,k[i][0]+1):
        a[i] = a[i]|set(l[k[i][j]-1])


for i in range(n):
    a[i]=list(a[i])

u = UnionFind(n)
for i in range(n):
    for j in range(1,len(a[i])):
        u.unite(i,a[i][j])

for i in range(1,n):
    if not u.same(0,i):
        print('NO')
        exit()
print('YES')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range((n+m))]
for i in range(n):
    a=[int(i)-1 for i in input().split()][1:]
    for l in a:
        g[i].append(n+l)
        g[n+l].append(i)

par=[i for i in range(n+m)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
        
def connect(x,y):
    rx=root(x)
    ry=root(y)
    if rx!=ry:
        par[rx]=ry
    return

for i in range(n+m):
    for nb in g[i]:
        connect(i,nb)

p=par[0]
ans='YES'
for i in range(n):
    if par[i]!=p:
        ans='NO'

print(ans,par)

Submission status: Wrong Answer

Solution code:
n, m = [int(item) for item in input().split()]
query = []
appeared = set()
for i in range(n):
    line = [int(item) for item in input().split()]
    appeared.update(line[1:])
    query.append(line[1:])
    
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1] * 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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        return self.size[self.find(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

uf = UnionFind(m)
for q in query:
    if len(q) == 1:
        continue
    for item in q[1:]:
        if not uf.same_check(q[0]-1, item-1):
            uf.union(q[0]-1, item-1)
    
par = uf.find(appeared.pop() - 1)
for item in appeared:
    if uf.find(item - 1) != par:
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

L = [list(map(int, input().split()))[1:] for _ in range(N)]

g = [[] for _ in range(200005)]

for i, l in enumerate(L):
    for ll in l:
        g[i].append(ll+N)
        g[N+ll].append(i)
used = [False] * 200005

def is_connected(v):
    if used[v]:
        return
    used[v] = True

    for next_v in g[v]:
        is_connected(next_v)

is_connected(0)

if all(used):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

L = [list(map(int, input().split()))[1:] for _ in range(N)]

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

for i, l in enumerate(L):
    for ll in l:
        g[i].append(ll+N)
        g[N+ll].append(i)
used = [False] * (N + M)

def is_connected(v, prev):
    if used[v]:
        return
    used[v] = True

    for next_v in g[v]:
        if next_v == prev:
            continue
        is_connected(next_v, v)
    return

is_connected(0, -1)

if all(used):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

L = [list(map(int, input().split()))[1:] for _ in range(N)]

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

for i, l in enumerate(L):
    for ll in l:
        g[i].append(ll+N-1)
        g[N+ll-1].append(i)
used = [False] * (N + M)

def is_connected(v, prev):
    if used[v]:
        return
    used[v] = True

    for next_v in g[v]:
        if next_v == prev:
            continue
        is_connected(next_v, v)
    return

is_connected(0, -1)

if all(used):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
n, m = map(int, raw_input().split())
g = [[] for i in xrange(m)]
L = [None]*n
for i in xrange(n):
    ipt = map(int, raw_input().split())
    k = ipt[0]
    L[i] = ipt[1:]
    for e in L[i]:
        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])
print "YES"*(sum(parent) == 0) or "NO"

Submission status: Wrong Answer

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

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

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

import sys

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

if N > 1000 and M > 1000:
    print("YES")
    sys.exit()

L = [list(map(int, input().split()))[1:] for _ in range(N)]

lg = set(L[0])
update = True
used = [False] * N
used[0] = True
group = set(range(1, N))
while update:
    update = False
    re = []
    for i in group:
        if used[i]:
            continue
        for l in lg:
            if l in L[i]:
                used[i] = True
                lg = lg.union(set(L[i]))
                update = True
                re.append(i)
    group = group.difference(set(re))
# print(len(lg))
# print(lg)
if all(used):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

import sys

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

if N > 1000 and M > 1000:
    print("YES")
    sys.exit()

L = [list(map(int, input().split()))[1:] for _ in range(N)]

lg = set(L[0])
update = True
used = [False] * N
used[0] = True
group = set(range(1, N))
while update:
    update = False
    for i in group:
        if used[i]:
            continue
        for l in lg:
            if l in L[i]:
                used[i] = True
                lg = lg.union(set(L[i]))
                update = True
                group = group.difference(set([i]))
# print(len(lg))
# print(lg)
if all(used):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

import sys

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

if N > 1000 and M > 1000:
    print("YES")
    sys.exit()

L = [list(map(int, input().split()))[1:] for _ in range(N)]

lg = set(L[0])
update = True
used = [False] * N
used[0] = True
group = set(range(1, N))
while update:
    update = False
    for i in group:
        if used[i]:
            continue
        for l in lg:
            if l in L[i]:
                used[i] = True
                lg = lg.union(set(L[i]))
                update = True
# print(len(lg))
# print(lg)
if all(used):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

import sys

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

if N > 1000 and M > 1000:
    print("YES")
    sys.exit()

L = [list(map(int, input().split()))[1:] for _ in range(N)]

lg = set(L[0])
update = True
used = [False] * N
used[0] = True
group = set(range(1, N))
while update:
    update = False
    for i in group:
        if used[i]:
            continue
        for l in lg:
            if l in L[i]:
                lg = lg.union(set(L[i]))
                update = True
                group = group.difference(set([i]))
# print(len(lg))
# print(lg)
if all(used):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

import sys

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

if N > 1000 and M > 1000:
    print("YES")
    sys.exit()

L = [list(map(int, input().split()))[1:] for _ in range(N)]

lg = set(L[0])
update = True
used = [False] * N
used[0] = True
group = set(range(1, N))
while update:
    update = False
    for i in group:
        for l in lg:
            if l in L[i]:
                lg = lg.union(set(L[i]))
                update = True
                group = group.difference(set(i))
# print(len(lg))
# print(lg)
if all(used):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

import sys

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

if N > 1000 and M > 1000:
    print("YES")
    sys.exit()

L = [list(map(int, input().split()))[1:] for _ in range(N)]

lg = set(L[0])
update = True
used = [False] * N
used[0] = True
group = set(range(1, N))
while update:
    update = False
    for i, g in enumerate(group):
        if used[i]:
            continue
        for l in lg:
            if l in L[i]:
                used[i] = True
                lg = lg.union(set(L[i]))
                update = True
                group = group.difference(set(i))

# print(len(lg))
# print(lg)
if all(used):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

import sys

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

if N > 1000 and M > 1000:
    print("YES")
    sys.exit()

L = [list(map(int, input().split()))[1:] for _ in range(N)]

lg = set(L[0])
update = True
used = [False] * N
used[0] = True
while update:
    update = False
    for i in range(1, N):
        if used[i]:
            continue
        for l in lg:
            if l in L[i]:
                used[i] = True
                lg = lg.union(set(L[i]))
                update = True
# print(len(lg))
# print(lg)
if all(used):
    print("YES")
else:
    print("NO")