100 atcoder#ABC216D. [ABC216D] Pair of Balls

[ABC216D] Pair of Balls

Score : 400400 points

Problem Statement

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

These balls are contained in MM cylinders placed perpendicularly to the floor. Initially, the ii-th cylinder (1iM)(1 \leq i \leq M) contains kik_i balls, the jj-th of which from the top (1jki)(1 \leq j \leq k_i) has the color ai,ja_{i, j}.

Your objective is to empty all MM 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

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 2M2×1052 \leq M \leq 2 \times 10^5
  • 1ki (1iM)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)$
  • i=1Mki=2N\sum_{i=1}^{M} k_i = 2N
  • For every x (1xN)x\ (1 \leq x \leq N), there exists exactly two pairs of integers (i,j)(i,j) such that 1iM1 \leq i \leq M, 1jki1 \leq j \leq k_i, and ai,j=xa_{i,j}=x.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

NN MM

k1k_1

a1,1a_{1,1} a1,2a_{1,2} \ldots a1,k1a_{1,k_1}

k2k_2

a2,1a_{2,1} a2,2a_{2,2} \ldots a2,k2a_{2,k_2}

\hspace{2.1cm}\vdots

kMk_M

aM,1a_{M,1} aM,2a_{M,2} \ldots aM,kMa_{M,k_M}

Output

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

2 2
2
1 2
2
1 2
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: 11.
  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: 22.
2 2
2
1 2
2
2 1
No

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