1749A - Cowardly Rooks solution codeforces

 

Cowardly Rooks solution codeforces

A. Cowardly Rooks

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There's a chessboard of size n×n$n\times n$. m$m$ rooks are placed on it in such a way that:

• no two rooks occupy the same cell;
• no two rooks attack each other.

A rook attacks all cells that are in its row or column.

Is it possible to move exactly one rook (you can choose which one to move) into a different cell so that no two rooks still attack each other? A rook can move into any cell in its row or column if no other rook stands on its path.

Input

The first line contains a single integer t$t$ (1≤t≤2000$1\le t\le 2000$) — the number of testcases.

The first line of each testcase contains two integers n$n$ and m$m$ (1≤n,m≤8$1\le n,m\le 8$) — the size of the chessboard and the number of the rooks.

The i$i$-th of the next m$m$ lines contains two integers xi$x_i$ and yi$y_i$ (1≤xi,yi≤n$1\le x_i,y_i\le n$) — the position of the i$i$-th rook: xi$x_i$ is the row and yi$y_i$ is the column.

No two rooks occupy the same cell. No two rooks attack each other.

Output

For each testcase, print "YES" if it's possible to move exactly one rook into a different cell so that no two rooks still attack each other. Otherwise, print "NO".

Example

input

Copy

2
2 2
1 2
2 1
3 1
2 2

output

Copy

NO
YES

Note

In the first testcase, the rooks are in the opposite corners of a 2×2$2\times 2$ board. Each of them has a move into a neighbouring corner, but moving there means getting attacked by another rook.

In the second testcase, there's a single rook in a middle of a 3×3$3\times 3$ board. It has 4$4$ valid moves, and every move is fine because there's no other rook to attack it.