Connect

Time limit1sMemory limit128 MB

Summary

Determine whether the last of alternating Twixt pegs placed on a bounded board completes a connected path joining the placing player's two opposing endzones.

Level: Medium7 of 10
Topics: Graph, Union-find, Simulation, Geometry
Solved: No attempts yet

Problem

Your task is to decide whether a given sequence of moves in the board game Twixt ends with a winning move.

In this version of the game the board size may vary. Pegs are placed at integer coordinates in the range $[0, N]$ . Two players, Black and White, each use pegs of their own color. Black always moves first, and the players then alternate, each move placing one peg on an unoccupied position $(x, y)$ .

Black's endzones are the lines where $x = 0$ or $x = N$ ; White's endzones are the lines where $y = 0$ or $y = N$ . Neither player may place a peg inside the other player's endzones.

After each move, the peg just placed is connected by a segment to every peg of the same color that is a chess knight's move away (a difference of $2$ in one coordinate and $1$ in the other), provided the new segment touches no previously added segment except at a shared endpoint. If a new segment would cross or overlap any existing segment (of either color), that segment is simply not added.

Play stops after a winning move: the move by which a player's segments first complete a connected path linking that player's two endzones.

For example, on a board with $N = 4$ : after the moves $(0,2)$ , $(2,4)$ , $(4,2)$ and then $(3,2)$ , Black playing $(2,3)$ is a poor move, while Black playing $(2,1)$ instead would win the game. As another example, on a board with $N = 7$ , Black wins in 11 moves: $(0,3)$ , $(6,5)$ , $(3,2)$ , $(5,7)$ , $(7,2)$ , $(4,4)$ , $(5,3)$ , $(5,2)$ , $(4,5)$ , $(4,0)$ , $(2,4)$ .

Input

The input contains from 1 to 20 datasets, followed by a line containing only two zeros, 0 0.

The first line of each dataset contains the maximum coordinate $N$ and the total number of moves $M$ , where $3 < N < 21$ , $4 < M < 250$ , and $M$ is odd. The remaining numbers of the dataset are $M$ coordinate pairs, given with one or more pairs per line and all numbers separated by spaces.

Because $M$ is odd, Black always makes the last move. All data are legal, and no winning move ever occurs before the last move.

Output

For each dataset, print a single line containing yes if the last move is a winning move, and no otherwise.

Examples3

Example 1

Input

4 5
0 2 2 4 4 2 3 2 2 3
4 5
0 2 2 4 4 2 3 2 2 1
7 11
0 3 6 5 3 2 5 7 7 2 4 4
5 3 5 2 4 5 4 0 2 4
0 0

Expected output

no
yes
yes

Example 2
Input
```
4 5
0 2 2 4 4 2 3 2 2 1
0 0
```
Expected output
```
yes
```
Example 3
Input
```
4 5
0 2 1 1 2 1 3 3 4 2
0 0
```
Expected output
```
yes
```