D - 球的配对

得分：400分

题目描述

我们有 $2N$ 个球。每个球的颜色由一个介于 $1$ 和 $N$ 之间的整数表示。对于每种颜色，都有两个球是该颜色。

这些球被放在鞍座上放置在地板上。初始时，第 $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。

2 2
2
1 2
2
1 2

Yes

可以按照以下方式达成目标。

1. 选择第一个和第二个鞍座，从其中取出最上面的球，这是允许的，因为取出的球是相同的颜色：$1$。
2. 选择第一个和第二个鞍座，从其中取出最上面的球，这是允许的，因为取出的球是相同的颜色：$2$。

2 2
2
1 2
2
2 1

No

根本无法进行任何操作，这意味着不可能实现清空 $M$ 个鞍座的目标。