Problem F
Fizzy Flow

The International Drinks Institute (IDI) is hosting its annual programming competition IDI Open at their headquarters. While the main event is of course the competition, every team really enjoys all the free drinks they get during the competition. You see, every table has taps so the teams can dispense as much as they like.

These taps aren’t connected to local kegs however. Instead, each table connects via pipes under the floor to up to $3$ out of $N$ big kegs. The kegs are positioned just outside the venue hall, distributed along its contiguous outer walls. Because the piping is laid on a single level, no two pipes can cross each other, nor can a pipe pass through a table it is not connected to. Furthermore, pipes cannot be routed outside the hall or behind the kegs to bypass one another. Note that pipes are never shared: a table has a direct, dedicated pipe to each of its kegs.

Figure 1: Visualisation of sample input 2.

Unfortunately, these big kegs have a big limitation: Each keg can only contain one flavour which is unique to that keg. While it can contain the sugared flavour or the sugar-free version, it can obviously not contain both at once. And since the participants have gotten their tables designated ahead of time, they are stuck with the flavours from the taps on their table.

However, they can request to have the drink from the kegs be sugared or sugar-free! Since there are multiple contestants, they may request a sugared version of one flavour and a sugar-free version of another.

The organisers of the event therefore ask every team whether they want sugar or not in the drink they get from the kegs, and want to make sure every team gets at least one of their requests fulfilled. Can you help the organisers figure out whether this is possible?

Input

The first line contains two integers $N$ and $M$, specifying the total number of big kegs and the number of contestant tables. The kegs are ordered in an anti-clockwise manner around the hall perimeter.

Then follow $M$ lines, one for each table. Each line starts with one integer $K_i$, then follows with $K_i$ integers $k_{i,1}, \ldots k_{i,K_i}$.

$|k_{i,j}|$ is the $j^{\text{th}}$ keg table $i$ is connected to. If $k_{i,j} > 0$, the team wants the sugared version of the flavour. If $k_{i,j} < 0$, they want the sugar-free version of the flavour.

Output

Output “YES” (without the quotes) if all teams are able to get at least one of their requests fulfilled, otherwise output “NO” (again without the quotes).

Limits

• $1 \leq N, M \leq 1200$

• $1 \leq K_i \leq 3$

• $1 \leq |k_{i,j}| \leq N$

• The kegs for each table are listed in increasing order: $|k_{i,j}| < |k_{i,l}|$ for all $0 < j < l \leq K_i$

• It is guaranteed that the pipes are laid out without crossing other pipes or tables, and that all of them are laid inside the venue hall.

2 2
2 1 2
1 -1

YES

3 4
1 1
2 -1 2
3 -1 -2 3
1 -3

NO