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:
import sys
from networkx.utils import UnionFind
def input(): return sys.stdin.readline().rstrip()


def main():
    n,m=map(int, input().split())
    lang=[[] for i in range(m+1)]
    for i in range(1,n+1):
        for talk in list(map(int, input().split()))[1:]:
            lang[talk].append(i)
    uf = UnionFind()
    for langs in lang:
        if len(langs) >=1:
            uf.union(*langs)
    print('Yes' if len(list(uf.to_sets()))==1 else 'No')
    




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[]
for i in range(n):
  l.append(list(map(lambda x:int(x)-1,input().split()))[1:])


d=[0 for i in range(m)]
for i in l[0]:
  d[i]=1

f=True
for i in range(1,n):
  ff=True
  for j in l[i]:
    if d[j]:
      ff=False
    d[j]=1
  if ff:
    f=False
    break


print("YES" if f else "NO")

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
G = [[] for _ in [0]*(N+M)]
for i in range(N):
    K, *L = map(int, input().split())
    for l in L:
        l = N+l-1
        G[i].append(l)
        G[l].append(i)


visited = [-1]*(N+M)


def dfs(v=0, d=4):
    if d == 0:
        return
    for u in G[v]:
        if visited[u] > d:
            continue
        visited[u] = d
        dfs(u, d-1)


visited[0] = 5
dfs()

for i in range(N):
    if visited[i] == -1:
        print('NO')
        break
else:
    print('YES')

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
G = [[] for _ in [0]*(N+M)]
for i in range(N):
    K, *L = map(int, input().split())
    for l in L:
        l = N+l-1
        G[i].append(l)
        G[l].append(i)


visited = [-1]*(N+M)


def dfs(v=0, d=4):
    if d == 0:
        return
    for u in G[v]:
        if visited[u] > d:
            continue
        visited[u] = d
        dfs(u, d-1)


dfs()
visited[i] = 5

for i in range(N):
    if visited[i] == -1:
        print('NO')
        break
else:
    print('YES')

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
G = [[] for _ in [0]*(N+M)]
for i in range(N):
    K, *L = map(int, input().split())
    for l in L:
        l = N+l-1
        G[i].append(l)
        G[l].append(i)


visited = [-1]*(N+M)


def dfs(v=0, d=4):
    if d == 0:
        return
    for u in G[v]:
        if visited[u] >= d:
            continue
        visited[u] = d-1
        dfs(u, d-1)


dfs()
visited[i] = 4

for i in range(N):
    if visited[i] == -1:
        print('NO')
        break
else:
    print('YES')

Submission status: Wrong Answer

Solution code:
def unite(x,y):
	rx=root(x)
	ry=root(y)
	if rank[rx]<rank[ry]:
		parent[rx]=ry
	else:
		parent[ry]=rx
		if rank[rx]==rank[ry]:
			rank[rx]+=1
def same(x,y):
	return root(x)==root(y)
def root(x):
	if x!=parent[x]:
		x=root(parent[x])
	return x
n,m=map(int,input().split())
parent=list(range(n+m))
rank=[0]*(n+m)
for i in range(n):
	l=list(map(int,input().split()))
	del l[0]
	for x in l:
		unite(n+x-1,i)
for i in range(n):
	if root(i)!=root(i+1):
		print("NO")
		exit()
print("YES")

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 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())
uf=UnionFind(m)
L=[0]*m
for i in range(n):
  A=list(map(int,input().split()))
  for j in range(len(A)-2):
    uf.union(A[j+1]-1,A[j+2]-1)
    L[A[j+1]-1]=1
    L[A[j+2]-1]=1
LL=[]
for i in range(m):
  if L[i]==0:
    continue
  LL.append(uf.find(i))
if len(set(LL))==1:
  print("YES")
else:
  print("NO")

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################
class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[x]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
    
    def __str__(self):
        rt=[i if j<0 else j for i,j in enumerate(self.table)]
        return str(rt)


show_flg=False
show_flg=True

ans=0
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)

uf=UnionFind(n+m)

for i in range(n+m):
    for nb in g[i]:
        uf.union(i,nb)
p=uf.table[0]

ans='YES'
for i in range(n):
    if uf._root(i)!=p:
        ans='NO'

print(ans)

Submission status: Wrong Answer

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

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

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

def main():
    ##########################################
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        ・復元なし
        """

        #最短のpathをたす


        class Edge():
            #重み付き有向辺

            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost

        def __init__(self, V):
            #引数Vは頂点数
            self.inf=10**20
            self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
            self. _E = 0 #辺の数
            self._V = V #頂点数

        #proparty - 辺の数
        def E(self):
            return self._E

        #proparty - 頂点数
        def V(self):
            return self._V

        def add(self, _from, _to, _cost):
            #2頂点と辺のコストを追加
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1

        def add2(self, _from, _to, _cost):
            #2頂点と辺のコスト（無向）を追加
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2

        def shortest_path(self,s):#,g):
            #始点sから頂点iまでの最短経路長のリストを返す
            que = [] #priority queue
            d = [self.inf] * self.V()

            #prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
            #復元で使う

            d[s] = 0
            heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加

            while len(que)!=0:
                #キューに格納されてある中で一番コストが小さい頂点を取り出す
                cost,v = heapq.heappop(que)

                #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
                if d[v] < cost:
                    continue

                #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
                for i in range(len(self.G[v])):
                    e = self.G[v][i] #vのi個目の隣接辺
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost #更新

                        #prev[e.to] = v
                        #復元で使う

                        heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加

            """#sからgまでの最短経路
            path = []
            pos = g #今いる場所，ゴールで初期化
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                #print("pos:",format(pos))
                pos = prev[pos]
            path.reverse()
            #print(path)"""

            return d#,path
    ########################
    
    N,M=MI()
    djk=Dijkstra(N+M)
    for i in range(N):
        L=LI()
        for j in range(1,L[0]+1):
            l=L[j]
            l-=1
            djk.add2(i,l+N,1)
            
    d=djk.shortest_path(0)
    Md=0
    Mi=0
    for i in range(N):
        if d[i]>Md:
            Md=d[i]
            Mi=i
        
    d2=djk.shortest_path(Mi)
    Md2=0
    Mi2=Mi
    for i in range(N):
        if d2[i]>Md2:
            Md2=d2[i]
            Mi2=i
            
    if Md2<=8:
        print("YES")
    else:
        print("NO")
        

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

    """
    n個の要素を0 ~ n - 1の番号で管理する。以下の属性およびメソッドを持つ。

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

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

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

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

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

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

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

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

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

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


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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

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

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


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

Submission status: Wrong Answer

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



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

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

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

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

Submission status: Wrong Answer

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(klkl[0][0])    

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

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

#n,m<=10**5


fuck=[0]*m

for item in list(map(int,input().split()))[1:]:
    fuck[item-1]=1

for _ in range(n-1):
    kl=list(map(int,input().split()))[1:]
    flag=0
    for item in kl:
        item-=1
        if fuck[item]==1:
            flag=1
    
    if flag==1:
        for item in kl:
            item-=1
            fuck[item]=1
    else:
        for item in kl:
            item-=1
            if fuck[item]==0:
                fuck[item]=-1
    #print(flag,kl)
    #print(fuck)

if -1 in fuck:
    print("NO")
else:
    print("YES")

Submission status: Wrong Answer

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

#n,m<=10**5


fuck=[0]*m

for item in list(map(int,input().split()))[1:]:
    fuck[item-1]=1

for _ in range(n-1):
    kl=list(map(int,input().split()))
    flag=0
    for item in kl[1:]:
        item-=1
        if fuck[item]==1:
            flag=1
    
    if flag==1:
        for item in kl:
            item-=1
            fuck[item]=1
    else:
        for item in kl:
            item-=1
            if fuck[item]==0:
                fuck[item]=-1
    #print(flag,kl)
    #print(fuck)

if -1 in fuck:
    print("NO")
else:
    print("YES")

Submission status: Wrong Answer

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(((e,f)),[n+m]*2))[1][:n]::2])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    N,M=pin()
    lang=[set()for i in range(M)]
    for i in range(N):
        k,*l=pin()
        for j in l:
            lang[j-1].add(i)
        #print(l) 
        #print(lang)
        temp=set()

    way=[set()for i in range(N)]
    for sp in lang:
        if len(sp)<2:continue
        for x in sp:
            way[x]=way[x].union(sp)
    #print(way)

    #dfs
    cond=0
    stack=[0]
    for xyz in range(10**6):
        if stack==[]:break

        temp=stack.pop()
        if temp==N-1:
            cond=1
            break
        for w in way[temp]:
            if w==temp:continue
            stack.append(w)
    print(["NO","YES"][cond])
#%%submit!
resolve()

Submission status: Wrong Answer

Solution code:
import sys
import collections

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


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


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

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

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

        if x == y:
            return

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

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

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

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

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

    def roots(self):
        return [i for i, x in enumerate(self._root_table) if x == i]

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

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

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


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

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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, readline().split())
uf = UnionFind(m)
kl = [list(map(int, readline().split())) for _ in range(n)]
for kl_ in kl:
    for bf, af in zip(kl_[1:], kl_[2:]):
        uf.union(bf - 1, af - 1)
check = set()
for kl_ in kl:
    for x in kl_:
        check.add(uf.find(x - 1))
print('YES' if len(check) == 1 else 'NO')

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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, readline().split())
uf = UnionFind(m + 1)
kl = [list(map(int, readline().split())) for _ in range(n)]
for kl_ in kl:
    for bf, af in zip(kl_[1:], kl_[2:]):
        uf.union(bf, af)
check = set()
for kl_ in kl:
    for x in kl_:
        check.add(uf.find(x))
print('YES' if len(check) == 1 else 'NO')

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
check = set(list(map(int, readline().split()))[1:])
for _ in range(n - 1):
    kl = list(map(int, readline().split()))
    kl = set(kl[1:])
    if check & kl:
        check |= kl
    else:
        print('NO')
        exit()
print('YES')

Submission status: Wrong Answer

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

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

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

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


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

    if g_num[N] == N:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[[]for i in range(m+1)]
par=[-1 for i in range(n)]
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(n):
    ll=[int(j) for j in input().split()[1:]]
    for j in ll:
        for k in l[j]:
            if root(i)!=root(k):
                connect(i,k)
        l[j].append(i)

if len(set(par))==2:
    print("YES")
else:
    print("NO")