Pair of Balls

题目描述

我们有 $2N$ 个球。每个球的颜色由 $1$ 到 $N$（含）之间的整数表示。对于每一个 $N$ 个颜色中的颜色，恰好有两个该颜色的球。 这些球被放在垂直于地面的 $M$ 个圆柱中。最初，第 $i$ 个圆柱 $(1 \leq i \leq M)$ 包含 $k_i$ 个球，从上往下第 $j$ 个球 $(1 \leq j \leq k_i)$ 的颜色为 $a_{i, j}$。 你的目标是通过重复下述操作将所有 $M$ 个圆柱清空。

选择两个不同的非空圆柱，并从每个圆柱中取出最上面的一个球。这里，被取出的两个球必须具有相同的颜色。

判断该目标是否可达成。

输入格式

输入从标准输入按以下格式给出： $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$。

2 2
2
1 2
2
1 2

Yes

2 2
2
1 2
2
2 1

No

提示

$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$。 输入中的所有值均为整数。可以这样完成目标。

选择第一和第二个圆柱，从它们各自取出最上面的球，这是允许的因为被取出的球颜色相同：$1$。 选择第一和第二个圆柱，从它们各自取出最上面的球，这是允许的因为被取出的球颜色相同：$2$。

不能进行任何操作，这意味着不可能实现将 $M$ 个圆柱清空的目标。

标签: AtCoder|abc216D

来源

AtCoder|abc216D