题目描述
2N 個のボールがあります。各ボールには 1 以上 N 以下の整数によって表される色が塗られており、各色で塗られたボールはちょうど 2 個ずつ存在します。
これらのボールが、底が地面と平行になるように置かれた M 本の筒に入れられています。はじめ、i (1 ≤ i ≤ M) 本目の筒には ki 個のボールが入っており、上から j (1 ≤ j ≤ ki) 番目のボールの色は ai, j です。
あなたの目標は、以下の操作を繰り返すことで M 本の筒全てを空にすることです。
- 異なる 2 本の空でない筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。ここで、取り出して捨てた 2 つのボールは同じ色で塗られている必要がある。
目標が達成可能かを判定してください。
输入格式
入力は以下の形式で標準入力から与えられる。
N M k1 a1,1 a1,2 … a1,k1 k2 a2,1 a2,2 … a2,k2 ⋮ kM aM,1 aM,2 … aM,kM
输出格式
目標が達成可能なら Yes
を、達成不可能なら No
を出力せよ。
题目大意
有 m 个栈,栈里面的小球有 n 种颜色,每种颜色各有 2 个,共 2n 个小球。
每次可以取出栈顶 2 个颜色相同的小球,问能不能把小球取完。
能取完输出 Yes
,否则输出 No
。
1≤n≤2×105,2≤m≤2×105。
2 2
2
1 2
2
1 2
Yes
2 2
2
1 2
2
2 1
No
提示
制約
- 1 ≤ N ≤ 2 × 105
- 2 ≤ M ≤ 2 × 105
- 1 ≤ ki (1 ≤ i ≤ M)
- $ 1\ \leq\ a_{i,j}\ \leq\ N\ (1\ \leq\ i\ \leq\ M,1\ \leq\ j\ \leq\ k_i) $
- ∑i=1M ki = 2N
- 全ての x (1 ≤ x ≤ N) について、1 ≤ i ≤ M かつ 1 ≤ j ≤ ki かつ ai,j=x なる整数の組 (i,j) はちょうど 2 つ存在する
- 入力は全て整数
Sample Explanation 1
以下のように操作を行えばよいです。 1. 1 つ目の筒と 2 つ目の筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。捨てられるボールの色は共に 1 であり等しいので、この操作は有効である。 2. 1 つ目の筒と 2 つ目の筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。捨てられるボールの色は共に 2 であり等しいので、この操作は有効である。
Sample Explanation 2
そもそも一度も操作を行うことができないため、目標を達成する、すなわち M 本の筒全てを空にすることは不可能です。