AT_abc216_d [ABC216D] Pair of Balls

题目描述

有 $2N$ 个球。每个球被涂上了一个用 $1$ 到 $N$ 之间的整数表示的颜色，并且每种颜色恰好有 $2$ 个球。

这些球被放入了 $M$ 根底部与地面平行的筒中。最开始，第 $i$ 根筒（$1 \leq i \leq M$）中有 $k_i$ 个球，从上到下第 $j$ 个球的颜色为 $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}$
$\vdots$
$k_M$ $a_{M,1}$ $a_{M,2}$ $\ldots$ $a_{M,k_M}$

输出格式

如果目标可以达成，输出 Yes；否则输出 No。

输入输出样例 #1

输入 #1

2 2
2
1 2
2
1 2

输出 #1

Yes

输入输出样例 #2

输入 #2

2 2
2
1 2
2
2 1

输出 #2

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

可以按如下方式进行操作：

1. 选择第 1 根筒和第 2 根筒，各自取出最上面的球并丢弃。两球颜色均为 $1$，操作有效。
2. 选择第 1 根筒和第 2 根筒，各自取出最上面的球并丢弃。两球颜色均为 $2$，操作有效。

样例解释 2

由于无法进行任何一次操作，因此无法达成目标，即无法将所有 $M$ 根筒都变为空。

由 ChatGPT 4.1 翻译