分数: 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 无法相互通信。