/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
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 つのボールは同じ色で塗られている必要がある。
目標が達成可能かを判定してください。
制約
- 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 つ存在する
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
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 つ目の筒と 2 つ目の筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。捨てられるボールの色は共に 1 であり等しいので、この操作は有効である。
- 1 つ目の筒と 2 つ目の筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。捨てられるボールの色は共に 2 であり等しいので、この操作は有効である。
入力例 2
2 2 2 1 2 2 2 1
出力例 2
No
そもそも一度も操作を行うことができないため、目標を達成する、すなわち M 本の筒全てを空にすることは不可能です。
Score : 400 points
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.
- 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.
- 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.