[ABC216D] Pair of Balls
题意翻译
有 $m$ 个栈,栈里面的小球有 $n$ 种颜色,每种颜色各有 $2$ 个,共 $2n$ 个小球。
每次可以取出栈顶 $2$ 个颜色相同的小球,问能不能把小球取完。
能取完输出 `Yes`,否则输出 `No`。
$1 \leq n \leq 2 \times 10^5$,$2 \leq m \leq 2 \times 10^5$。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc216/tasks/abc216_d
$ 2N $ 個のボールがあります。各ボールには $ 1 $ 以上 $ N $ 以下の整数によって表される色が塗られており、各色で塗られたボールはちょうど $ 2 $ 個ずつ存在します。
これらのボールが、底が地面と平行になるように置かれた $ M $ 本の筒に入れられています。はじめ、$ i\ (1\ \leq\ i\ \leq\ M) $ 本目の筒には $ k_i $ 個のボールが入っており、上から $ j\ (1\ \leq\ j\ \leq\ k_i) $ 番目のボールの色は $ a_{i,\ j} $ です。
あなたの目標は、以下の操作を繰り返すことで $ M $ 本の筒全てを空にすることです。
- 異なる $ 2 $ 本の空でない筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。ここで、取り出して捨てた $ 2 $ つのボールは同じ色で塗られている必要がある。
目標が達成可能かを判定してください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ 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
输入样例 #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) $ について、$ 1\ \leq\ i\ \leq\ M $ かつ $ 1\ \leq\ j\ \leq\ k_i $ かつ $ a_{i,j}=x $ なる整数の組 $ (i,j) $ はちょうど $ 2 $ つ存在する
- 入力は全て整数
### Sample Explanation 1
以下のように操作を行えばよいです。 1. $ 1 $ つ目の筒と $ 2 $ つ目の筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。捨てられるボールの色は共に $ 1 $ であり等しいので、この操作は有効である。 2. $ 1 $ つ目の筒と $ 2 $ つ目の筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。捨てられるボールの色は共に $ 2 $ であり等しいので、この操作は有効である。
### Sample Explanation 2
そもそも一度も操作を行うことができないため、目標を達成する、すなわち $ M $ 本の筒全てを空にすることは不可能です。