102163: [AtCoder]ABC216 D - Pair of Balls

Problem Statement

We have $2N$ balls. Each ball has a color represented by an integer between $1$ and $N$ (inclusive). For each of the $N$ colors, there are exactly two balls of that color.

These balls are contained in $M$ cylinders placed perpendicularly to the floor. Initially, the $i$-th cylinder $(1 \leq i \leq M)$ contains $k_i$ balls, the $j$-th of which from the top $(1 \leq j \leq k_i)$ has the color $a_{i, j}$.

Your objective is to empty all $M$ cylinders by repeating the following operation.

• Choose two different non-empty cylinders and remove the topmost ball from each of them. Here, the two balls removed must be of the same color.

Determine whether the objective is achievable.

Constraints

• $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$
• For every $x\ (1 \leq x \leq N)$, there exists exactly two pairs of integers $(i,j)$ such that $1 \leq i \leq M$, $1 \leq j \leq k_i$, and $a_{i,j}=x$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$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}$

Output

If the objective is achievable, print Yes; otherwise, print No.

Sample Input 1

2 2
2
1 2
2
1 2

Sample Output 1

Yes

The objective can be achieved as follows.

1. Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: $1$.
2. Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: $2$.

Sample Input 2

2 2
2
1 2
2
2 1

Sample Output 2

No

No operation can be done at all, which means it is impossible to achieve the objective of emptying the $M$ cylinders.

问题描述

我们有$2N$个球。每个球都有一个用1到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. 选择第一个和第二个圆筒，从每个圆筒中移除顶部的球，这是允许的，因为移除的球具有相同的颜色：$1$。
2. 选择第一个和第二个圆筒，从每个圆筒中移除顶部的球，这是允许的，因为移除的球具有相同的颜色：$2$。

样例输入2

2 2
2
1 2
2
2 1

样例输出2

No

根本无法执行任何操作，这意味着无法实现清空$M$个圆筒的目标。