Knights

Time limit1sMemory limit128 MB

Summary

Decide if the first player wins a combinatorial game where all knights with restricted moves must move simultaneously each turn until none can move.

Level: Hard8 of 10
Topics: Game theory, Graph, Math
Solved: No attempts yet

Problem

Alice and Bob play a game on an $N \times N$ chessboard. Initially $K$ black knights are placed on it. No two knights start on the same square, and every knight has at least one legal move at the start.

The players alternate turns and Alice moves first. On each turn the current player must move every knight that still has at least one legal move; a knight with no legal move stays on its square. From square $(x, y)$ a knight may move to any of these four squares, as long as the destination stays on the board (both coordinates between $1$ and $N$ ):

$(x+1,\; y-2)$
$(x-1,\; y-2)$
$(x-2,\; y+1)$
$(x-2,\; y-1)$

Several knights may occupy the same square. The first player who cannot move any knight (every knight is stuck) loses. Assume both players play optimally.

Determine whether Alice, who moves first, can win.

Input

The first line contains two integers $K$ and $N$ ( $1 \le K \le 200000$ , $1 \le N \le 300$ ).

Each of the next $K$ lines contains two integers $x_i$ and $y_i$ ( $1 \le x_i, y_i \le N$ ) — the square of the $i$ -th knight. No two knights share a square, and every knight has at least one legal move.

Output

Print a single line containing YES if Alice can force a win, or NO otherwise.

Examples5

Example 1
Input
```
2 3
2 3
3 2
```
Expected output
```
YES
```
Example 2
Input
```
3 4
2 3
3 2
4 4
```
Expected output
```
NO
```
Example 3
Input
```
1 6
1 3
```
Expected output
```
YES
```
Example 4
Input
```
1 6
1 5
```
Expected output
```
NO
```
Example 5
Input
```
1 3
3 3
```
Expected output
```
YES
```