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

Solution code:
N,M=map(int,input().split())
from collections import defaultdict
dist=[d]*N
branch=defaultdict(set)
lang=defaultdict(set)
inp=[]
for i in range(N):
    X=list(map(int,input().split()))
    for k in range(X[0]):
        lang[X[k+1]]|={i}
    inp.append(X[1:])
for i in range(N):
    for l in inp[i]:
        branch[i]|=lang[l]
checked={0}
check={0}
while len(check)>0:
    now=check.pop()
    check|=branch[now]-checked
    checked|=branch[now]
    if len(checked)==N:
        break
if len(checked)==N:
    print('YES')
else:
    print('NO')

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
H = []
L = [[] for k in range(M+1)]

for k in range(N):
    P = list(map(int,input().split()))[1:]
    H.append(P)
    for e in P:
        L[e].append(k+1)

G = [0 for k in range(N+1)]
G[1] = 1
Q = [H[0]]
while len(Q) > 0:
    ima = Q.pop()
    if len(ima) == 1 and G[ima[0]] == 1:
        pass
    for tsugi in ima:
        for e in L[tsugi]:
            if G[e] == 0:
                G[e] = 1
                if len(H[e-1]) > 1:
                    Q.append(H[e-1])

for k in range(1,N+1):
    if G[k] == 0:
        print("NO")
        exit(0)
print("YES")

Submission status: Runtime Error

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

parent = [i for i in range(N + M)]
rank = [0] * (N + M)


def find(i):
    if parent[i] == i:
        return i
    else:
        parent[i] = find(parent[i])
        return parent[i]


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


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return

    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


for i in range(N):
    P = list(map(int, input().split()))
    n = P[0]
    for j in range(1, n + 1):
        unite(N + i, P[j] - 1)


k = find(0)
for i in range(N):
    if k != find(i):
        print('NO')
        exit()

print('YES')

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
graph = [[] for i in range(M)]
for i in range(N):
    L = list(map(int, input().split()))
    for j in range(1,L[0]+1):
        graph[L[j]-1].append(i)

def root(x):
    if par[x] == x:
        return(x)
    else:
        y = root(par[x])
        par[x] = y
        return y
def unite(x,y):
    x = root(x)
    y = root(y)
    if x==y:
        return
    par[x] = y

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

par = [i for i in range(N)]
for i in range(M):
    lang = graph[i]
    if len(lang) > 1:
        for j in range(1,len(lang)):
            unite(lang[0], lang[j])

flag = True
for i in range(1, N):
    if not same(0, i):
        flag = False
        break
if flag:
    print('YES')
else:
    print('NO')

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
graph = [[] for i in range(M)]
for i in range(N):
    L = list(map(int, input().split()))
    for j in range(1,L[0]+1):
        graph[L[j]-1].append(i)

def root(x):
    if par[x] == x:
        return(x)
    else:
        par[x] = root(par[x])
        return(par[x])
def unite(x,y):
    x = root(x)
    y = root(y)
    if x==y:
        return
    par[x] = y

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

par = [i for i in range(N)]
for i in range(M):
    lang = graph[i]
    if len(lang) > 1:
        for j in range(1,len(lang)):
            unite(lang[0], lang[j])

flag = True
for i in range(1, N):
    if not same(0, i):
        flag = False
        break
if flag:
    print('YES')
else:
    print('NO')

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
graph = [[] for i in range(M)]
for i in range(N):
    L = list(map(int, input().split()))
    if L[0] >= 1:
        for j in range(1,L[0]+1):
            graph[L[j]-1].append(i)

def root(x):
    if par[x] == x:
        return(x)
    else:
        par[x] = root(par[x])
        return(par[x])
def unite(x,y):
    x = root(x)
    y = root(y)
    if x==y:
        return
    par[x] = y
def same(x,y):
    return root(x) == root(y)

par = [i for i in range(N)]
for i in range(M):
    lang = graph[i]
    if len(lang) > 1:
        for j in range(1,len(lang)):
            unite(lang[0], lang[j])
flag = True
for i in range(N-1):
    if not same(i, i+1):
        flag = False
        break
if flag:
    print('YES')
else:
    print('NO')

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
graph = [[] for i in range(M)]
for i in range(N):
    L = list(map(int, input().split()))
    for j in range(1,L[0]+1):
        graph[L[j]-1].append(i)

def root(x):
    if par[x] == x:
        return(x)
    else:
        par[x] = root(par[x])
        return(par[x])
def unite(x,y):
    x = root(x)
    y = root(y)
    if x==y:
        return
    par[x] = y
def same(x,y):
    return root(x) == root(y)

par = [i for i in range(N)]
for i in range(M):
    lang = graph[i]
    if len(lang) > 1:
        for j in range(1,len(lang)):
            unite(lang[0], lang[j])
flag = True
for i in range(N-1):
    if not same(i, i+1):
        flag = False
        break
if flag:
    print('YES')
else:
    print('NO')

Submission status: Runtime Error

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+n-i)
        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: Runtime Error

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].append(i)
t=[False]*n
def g(x):
    if not t[x]:
        t[x]=False:
            for i in a[x]:
                for j in a[i+n]:
                    g(j)
g(0)
if all(t):
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

Solution code:
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)

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

Solution code:
N, M = map(int, input().split())
parent = [i for i in range(N + M)]
def find(x):
    if x == parent[x]:
        return x
    parent[x] = find(parent[x])
    return parent[x]

def unite(x, y):
    x, y = find(x), find(y)
    if x == y:
        return
    parent[y] = x
for i in range(N):
    for l in list(map(int, input().split()))[1:]:
        # 言語はparentの後半
        unite(i, N + l - 1)
if all(find(0) == find(i) for i in range(N)):
    print('YES')
else:
    print('NO')

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
P = [[] for i in range(N)]
L = [[] for i in range(M)]
for i in range(N):
    I = list(map(int, input().split()))
    for l in I[1:]:
        P[i].append(l-1)
        L[l-1].append(i)

P_visited = [0] * N
L_visited = [0] * M


# flgが立っていれば、人を見ているとする
def dfs(n, flg):
    if flg:
        P_visited[n] = 1
        for l in P[n]:
            if not L_visited[l]:
                dfs(l, flg ^ 1)
    else:
        L_visited[n] = 1
        for p in L[n]:
            if not P_visited[p]:
                dfs(p, flg ^ 1)


dfs(0, 1)
print("YES" if all(P_visited) else "NO")

Submission status: Runtime Error

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

par = [i for i in range(N+M)]
def root(a):
    if par[a] == a: return a
    par[a] = root(par[a])
    return par[a]

def same(a,b):
    return root(a) == root(b)

def unite(a,b):
   ra,rb = root(a),root(b)
   if ra == rb: return
   par[ra] = rb

for i in range(N):
    src = list(map(lambda x:int(x)-1,input().split()))
    if len(src) == 1: continue
    for j in src[1:]:
        unite(i,N+j)

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

Submission status: Runtime Error

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

par = [i for i in range(N+M)]
def root(a):
    if par[a] == a: return a
    return root(par[a])

def same(a,b):
    return root(a) == root(b)

def unite(a,b):
   ra,rb = root(a),root(b)
   if ra == rb: return
   par[ra] = rb

for i in range(N):
    src = list(map(lambda x:int(x)-1,input().split()))
    for j in src[1:]:
        unite(i,N+j)

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from unionfind import unionfind
N, M = map(int, input().split())
u = unionfind(N + M)
for i in range(N):
    L = [int(x) - 1 for x in input().split()]
    L[0] += 1
    for j in range(L[0]):
        u.unite(L[j + 1], M + i)

ans = True
for i in range(N):
    if not u.issame(M, M + i):
        ans = False
print(('NO', 'YES')[ans])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
N = int(input())

sum = 0
m = 0
for i in range(1, 10**3 + 1):
    sum += i
    if sum >= N:
        m = i
        break

sum = N
for i in range(1, m + 1)[::-1]:
    if sum - i >= 0:
        sum -= i
        print(i)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env pypy3


class UnionFind(object):

    def __init__(self, number_of_nodes):
        self.par = list(range(number_of_nodes))
        self.rank = [0] * number_of_nodes

    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r

    def in_the_same_set(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    n, m = (int(x) for x in input().split())
    assert n <= 1000 and m <= 1000
    speakers = [[] for _ in range(m)]
    for contestant in range(n):
        languages = [int(x) - 1 for x in input().split()][1:]
        for language in languages:
            speakers[language].append(contestant)
    uf = UnionFind(n)
    for lang_speakers in speakers:
        for i in range(len(lang_speakers) - 1):
            uf.unite(lang_speakers[i], lang_speakers[i + 1])
    for i in range(n):
        if not uf.in_the_same_set(0, i):
            print("NO")
            break
    else:
        print("YES")


if __name__ == '__main__':
    main()