← 返回题目列表

AtCoder · codefestival_2016_final_c

C. 解读

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

在一个遥远的星球上, 使用 M 语言。它们方便地编号 1 通过 M.

对于 代码节 20XX 在这个星球上举行, N 参与者来自世界各地。

的 i-th (1≦i≦N) 参与者可以发言 K_i 语言编号 L_{i,1}, L_{i,2}, ..., L_{i,{}K_i}.

两名参与者 A 和 B 可以 沟通 当且仅当满足以下条件之一时彼此 :

  • 存在一种语言 A 和 B 可以说话。
  • 存在参与者 X 两者 A 和 B 可以通讯。

判断是否全部 N 参与者可以与所有其他参与者进行通信。

约束

  • 2≦N≦10^5
  • 1≦M≦10^5
  • 1≦K_i≦M
  • (所有的总和 通过满足以下条件的测试集将获得 K_i)≦10^5
  • 1≦L_{i,j}≦M
  • L_{i,1}, L_{i,2}, ..., L_{i,{}K_i} 两两不同。

部分分数

  • 200 积分: N≦1000, M≦1000 和 (所有的总和 通过满足以下条件的测试集将获得 K_i)≦1000.
  • 附加 在没有额外限制的情况下通过测试集将获得 200 分数。

输入

输入由标准输入按以下格式给出:

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}

输出

如果全部 N 参与者可以与所有其他参与者交流,打印 YES。否则,打印 NO.


示例输入 1

4 6
3 1 2 3
2 4 2
2 4 6
1 6

示例输出 1

YES

任意两个参与者都可以相互通信,如下所示:

  • 参与者 1 和 2:两人都会说语言 2.
  • 参与者 2 和 3:两人都会说语言 4.
  • 参与者 1 和 3:两者都可以与参与者通信 2.
  • 参与者 3 和 4:两人都会说语言 6.
  • 参与者 2 和 4:两者都可以与参与者通信 3.
  • 参与者 1 和 4:两者都可以与参与者通信 2.

请注意,可能存在没有参与者说的语言。


示例输入 2

4 4
2 1 2
2 1 2
1 3
2 4 3

示例输出 2

NO

例如,参与者 1 和 3 无法相互通信。