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:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


n, m = map(int, input().split())
l = []
for _ in range(n):
    k, *ls = map(int, input().split())
    l.append(ls)

uf = UnionFind(m)

cnt = [0] * m
for li in l:
    for e1, e2 in zip(li, li[1:]):
        e1 -= 1
        e2 -= 1
        cnt[e1] = 1
        cnt[e2] = 1
        uf.unite(e1, e2)

if max(uf.size) >= sum(cnt):
    ans = "YES"
else:
    ans = "NO"

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


n, m = map(int, input().split())
l = []
for _ in range(n):
    k, *ls = map(int, input().split())
    l.append(ls)

uf = UnionFind(m)

cnt = [0] * m
for li in l:
    for e1, e2 in zip(li, li[1:]):
        e1 -= 1
        e2 -= 1
        cnt[e1] = 1
        cnt[e2] = 1
        uf.unite(e1, e2)

if max(uf.size) == sum(cnt):
    ans = "YES"
else:
    ans = "NO"

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)


def unite(par, i, j):
    j = get_par(par, j)
    par[j] = get_par(par, i)

def get_par(par, p):
    while par[p] != p:
        p = par[p]
    return par[p]

n,m = map(int, input().split())
lang = {}
for i in range(n):
    k,*l = map(int, input().split())
    for j in l:
        # print(i,j)
        if j not in lang:
            lang[j] = []
        lang[j].append(i)
# [print(k,v) for k,v in lang.items()]

par = [i for i in range(n)]
for k,v in lang.items():
    if len(v) == 1:
        continue
    a = v[0]
    for i in range(1,len(v)):
        aa = get_par(par, a)
        bb = get_par(par, v[i])
        if aa == bb:
            continue
        # unite
        if aa < bb:
            par[bb] = aa
        else:
            par[aa] = bb

print('YES' if len(set(par)) == 1 else 'NO')
# print(par)

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num, lang_num = map(int, input().split())

    graph_data = defaultdict(set)
    for i in range(num):
        data = list(map(int, input().split()))
        for ele in data[1:]:
            graph_data[ele].add(i + 1)


    parent_node = [i for i in range(num + 1)]

    for key, value in graph_data.items():
        min_ind = min([parent_node[aa] for aa in value])
        # min_ind = min(parent_node[min_ind], min_ind)
        for ele in value:
            parent_node[ele] = min_ind

    now_ind = parent_node[1]
    for ele in parent_node[2:]:
        if now_ind != ele:
            print('NO')
            sys.exit()

    print('YES')









if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num, lang_num = map(int, input().split())

    graph_data = defaultdict(set)
    for i in range(num):
        data = list(map(int, input().split()))
        for ele in data[1:]:
            graph_data[ele].add(i + 1)


    parent_node = [i for i in range(num + 1)]

    for key, value in graph_data.items():
        min_ind = min(list(value))
        min_ind = min(parent_node[min_ind], min_ind)
        for ele in value:
            parent_node[ele] = min_ind

    now_ind = parent_node[1]
    for ele in parent_node[2:]:
        if now_ind != ele:
            print('NO')
            sys.exit()

    print('YES')









if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from functools import reduce

class UnionFind:
    def __init__(self, node: int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]

    def find(self, x: int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> bool:
        if self.isSame(x, y):
            # print("x and y has already united")
            return False

        rx = self.find(x)
        ry = self.find(y)

        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]

            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

        return True

    def isSame(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


n, m = li()
lang = [[] for _ in range(m)]
for person in range(n):
    kl = list(li_())
    for langi in kl[1:]:
        lang[langi].append(person)

uf = UnionFind(n)
for langi in lang:
    if len(langi) < 2:
        continue

    reduce(uf.unite, langi)


for i in range(n):
    uf.find(i)

ok = True
for i in range(1, n):
    if uf.isSame(0, i):
        continue

    else:
        ok = False
        break

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

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from functools import reduce

class UnionFind:
    def __init__(self, node: int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]

    def find(self, x: int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> bool:
        if self.isSame(x, y):
            # print("x and y has already united")
            return False

        rx = self.find(x)
        ry = self.find(y)

        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]

            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

        return True

    def isSame(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


n, m = li()
lang = [[] for _ in range(m)]
for person in range(n):
    kl = list(li_())
    for langi in kl[1:]:
        lang[langi].append(person)

uf = UnionFind(n)
for langi in lang:
    if not langi:
        continue

    reduce(uf.unite, langi)

for i in range(n):
    uf.find(i)

if len(set(uf.par)) == 1:
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]
  
n,m=map(int,input().split())
t=UnionFind(m)
for _ in range(n):
  l=list(map(int,input().split()))
  if l[0]==1:
    t.Unite(l[1],l[1])
  else:
    for i in range(l[0]-1):
      t.Unite(l[1],l[2+i])
s=set()
for i in range(m+1):
  r=t.FindRoot(i)
  if r==i:
    continue
  s.add(r)
if len(s)==1:
  print('YES')
else:
  print('NO')

Submission status: Wrong Answer

Solution code:
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]
  
n,m=map(int,input().split())
t=UnionFind(m)
for _ in range(n):
  l=list(map(int,input().split()))
  if l[0]==1:
    t.Unite(0,l[1])
  else:
    for i in range(l[0]-1):
      t.Unite(l[1],l[2+i])
s=set()
for i in range(m):
  r=t.FindRoot(i)
  if r==i:
    continue
  else:
    s.add(r)
if len(s)==1:
  print('Yes')
else:
  print('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)

# 人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])

print('YES')
exit()

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:
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,len(k[i])):
        l[k[i][j]-1].append(i)

# 人iと会話が成立する人のset
a = [set() for i in range(n)]
for i in range(n):
    for j in range(1,len(k[i])):
        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:
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 = [[]for i in range(m)]

for i in range(n):
    for j in range(1,len(k[i])):
        l[k[i][j]-1].append(i)

a = [set() for i in range(n)]

for i in range(n):
    for j in range(1,len(k[i])):
        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**9)
n,m=map(int,input().split())
a=[[]for i in range(n+m)]
for i in range(n):
    s=list(map(int,input().split()))
    for j in s[1:]:
        a[i].append(j)
        a[n+j-1].append(i)
t=[False]*(n+m)
def g(x):
    t[x]=True
    for i in a[x]:
            if not t[i]:
                g(i)
g(0)
if all(t[:n]):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
a=[[]for i in range(n+m)]
for i in range(n):
    s=list(map(int,input().split()))
    for j in s[1:]:
        a[i].append(j)
        a[n+j-1].append(i)
t=[False]*(n+m)
def g(x):
    t[x]=True
    for i in a[x]:
            if not t[i]:
                g(i)
g(0)
if all(t[:n]):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
a=[[]for i in range(n+m)]
for i in range(n):
    s=list(map(int,input().split()))
    for j in s[1:]:
        a[i].append(j)
        a[n+j-1].append(i)
t=[False]*(n+m)
def g(x):
    t[x]=True
    for i in a[x]:
            if not t[x]:
                g(j)
g(0)
if all(t[:n]):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

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

people = []
lang = [[] for _ in range(m)]

for i in range(n):
  kl = list(map(int, input().split()))
  k = kl[0]
  people.append(kl[1:])
  for l in kl[1:]:
    lang[l-1].append(i)

print(people, lang)
visited = [False for _ in range(n)]

def dfs(i):
  if visited[i]:
    return
  else:
    visited[i] = True
    for l in people[i]:
      for nexp in lang[l-1]:
        dfs(nexp)

dfs(0)

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

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納　par[x] == x の時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0)
        self.rank = [0] * (n+1)
        # 各々の集合の要素数（根が代表して値を持っておく）
        self.count = [1] * (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
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            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 size(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]

n,m = map(int,input().split())
k = [set() for _ in range(m)]
U = UnionFind(n)
for i in range(n):
    l =list(map(lambda z:z-1, map(int,input().split())))
    for m in l[1:]:
        k[m].add(i)

for i in range(m):
    ki = list(k[i])
    if len(ki) == 0:
        continue
    for h in range(len(ki)):
        U.union(ki[h],ki[0])

if U.size(0) == n:
    print('YES')
else:
    print('NO')

Submission status: Wrong Answer

Solution code:
# Union-Findデータ構造
class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def find(self, x):
        if self.pars[x] == x: return x
        else:
            self.pars[x] = self.find(self.pars[x])
            return self.pars[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int, input().split())
UF = UnionFind(N+M)
for i in range(N):
    K, *Ls = map(int, input().split())
    for L in Ls:
        UF.union(i, L+N-1)

pars = [UF.find(i) for i in range(N)]
print('YES' if len(set(pars)) else 'NO')

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int,input().split())
K=[set() for i in range(M)]
table=[]
for i in range(N):
    L=[int(i)-1 for i in input().split()]
    k=L[0]
    M=L[1:]
    for m in M:
        K[m].add(i)
    table.append(M)
#print(table)
#print(K)
for i in range(N):
    Ket=set()
    Ket.add(i)
    for j in table[i]:
        Ket=Ket|K[j]
    if len(Ket)!=N:
        print('NO')
        sys.exit()
print('YES')

Submission status: Wrong Answer

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

UF = list(range(M + 1))


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


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


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


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

Submission status: Wrong Answer

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

UF = list(range(M + 1))


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


def unite(a, x, y):
    if find(a, x) < find(a, y):
        a[find(a, y)] = find(a, x)
    else:
        a[find(a, x)] = find(a, y)


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


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

Submission status: Wrong Answer

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

UF = list(range(M + 1))


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


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


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


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

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().split())
L=[[] for i in range(M)]
for i in range(N):
  for j,k in enumerate(input().split()):
    if j==0:
      continue
    L[int(k)-1].append(i)
G=[[] for i in range(N)]
for l in L:
  if len(l)>=2:
    for i in range(len(l)-1):
      if l[i+1] not in G[l[i]]:
        G[l[i]].append(l[i+1])
        G[l[i+1]].append(l[i])

V=[False]*N
n=1
dfs_stack=deque([0])
while dfs_stack:
  a=dfs_stack.popleft()
  if not V[a]:
    n+=1
    for b in G[a]:
      if not V[b]:
        dfs_stack.append(b)
  V[a]=True
if n>=N:
  print("YES")
else:
  print("NO")

Submission status: Wrong Answer

Solution code:
# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            #print("x and y has already united")
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
                
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)

from collections import defaultdict

dic = defaultdict(list)

n,m = li()

# 各言語を話せる人を登録
for i in range(n):
    l_list = li()
    for l in l_list[1:]:
        dic[l].append(i)
        
# union-findでマージしていく
uf = UnionFind(n)
for key in dic.keys():
    val = dic[key]
    print(len(val))
    for i in range(len(val)-1):
        if not uf.isSame(val[i], val[i+1]):
            uf.unite(val[i], val[i+1])
            print(uf.find(val[i]), uf.find(val[i+1]))

root = uf.find(0)
for i in range(n):
    print(uf.find(i))
    if uf.find(i) != root:
        print("NO")
        break
    
    if i == n-1:
        print("YES")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
class unionfind:
    def __init__(self, n):
        self.parent = [-1] * n
    def find(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.parent[x] > self.parent[y]: x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
    def issame(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int, input().split())
uf = unionfind(N + M)
for i in range(N):
    L = [int(x) - 1 for x in input().split()]
    for j in range(L[0] + 1):
        uf.unite(L[j + 1], M + i)
print(('NO', 'YES')[all(uf.issame(M, M + i) for _ in range(N))])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
class unionfind:
    def __init__(self, n):
        self.parent = [-1] * n
    def find(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.parent[x] > self.parent[y]: x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
    def issame(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int, input().split())
uf = unionfind(N + M)
for i in range(N):
    L = [int(x) - 1 for x in input().split()]
    for j in range(L[0] + 1):
        uf.unite(M + i, L[j + 1])
print(('NO', 'YES')[not any((not uf.issame(M, M + i) for _ in range(N)))])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
class unionfind:
    def __init__(self, n):
        self.parent = [-1] * n
    def find(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.parent[x] > self.parent[y]: x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
    def issame(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int, input().split())
uf = unionfind(N + M)
for i in range(N):
    L = [int(x) - 1 for x in input().split()]
    for j in range(L[0] + 1):
        uf.unite(M + i, L[j + 1])
print(('NO', 'YES')[all((uf.issame(M, M + i) for _ in range(N)))])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
class UnionFind():
    def __init__(self, size):
        self.table = [-1] * size

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

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


N, M = map(int, input().split())
uf = UnionFind(N + M)
ans = True
for i in range(N):
    L = [int(x) - 1 for x in input().split()]
    L[0] += 1
    for j in range(L[0]):
        uf.union(L[j + 1], M + i)
    if uf.find(M + i) != uf.find(M):
        ans = False

print(('NO', 'YES')[ans])

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
def readLine_int_list():return list(map(int, stdin.readline().split()))

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
        
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x==y: return
    if rank[x]<rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x]+=1
            
def same(x,y):
    return find(x)==find(y)
    
n,m = readLine_int_list()
v = n + m
par = [i for i in range(0, v)]
rank = [1] * v
def main():
    for i in range(n):
        for ii in readLine_int_list()[1:]:
           unite(i, ii)
           
    r = "YES"
    for i in range(0, n):
        if find(i) != find(0):
            r = "NO"
    print(r)
    
if __name__ == '__main__':
    main()