分数: 400 点
问题陈述
我们有 2N 球。每个球都有一个由介于之间的整数表示的颜色 1 和 N (含)。对于每个 N 颜色,该颜色正好有两个球。
这些球包含在 M 圆柱体垂直于地板放置。最初, i第气缸 (1 \leq i \leq M) 包含 k_i 球, j- 从上往下数 (1 \leq j \leq k_i) 有颜色 a_{i, j}.
你的目标是清空所有 M 通过重复以下操作来气缸。
- 选择两个不同的非空圆柱体并从每个圆柱体中取出最上面的球。这里,移除的两个球必须是相同颜色的。
确定目标是否可以实现。
约束
- 1 \leq N \leq 2 \times 10^5
- 2 \leq M \leq 2 \times 10^5
- 1 \leq k_i\ (1 \leq i \leq M)
- 1 \leq a_{i,j} \leq N\ (1 \leq i \leq M,1 \leq j \leq k_i)
- \sum_{i=1}^{M} k_i = 2N
- 对于每个 x\ (1 \leq x \leq N),恰好存在两对整数 (i,j) 这样 1 \leq i \leq M, 1 \leq j \leq k_i,和 a_{i,j}=x.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M
k_1
a_{1,1} a_{1,2} \ldots a_{1,k_1}
k_2
a_{2,1} a_{2,2} \ldots a_{2,k_2}
\hspace{2.1cm}\vdots
k_M
a_{M,1} a_{M,2} \ldots a_{M,k_M}
输出
如果目标可以实现,则打印 Yes;否则,打印 No.
示例输入 1
2 2 2 1 2 2 1 2
示例输出 1
Yes
该目标可以通过以下方式实现。
- 选择第一个和第二个圆柱体以移除每个圆柱体最上面的球,这是允许的,因为移除的球具有相同的颜色: 1.
- 选择第一个和第二个圆柱体以移除每个圆柱体最上面的球,这是允许的,因为移除的球具有相同的颜色: 2.
示例输入 2
2 2 2 1 2 2 2 1
示例输出 2
No
根本无法进行任何操作,也就是说无法达到清空的目的 M 气缸。