CF1749A Cowardly Rooks

There's a chessboard of size $ n \times n $ . $ 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.

The first line contains a single integer $ t $ ( $ 1 \le t \le 2000 $ ) — the number of testcases. The first line of each testcase contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 8 $ ) — the size of the chessboard and the number of the rooks. The $ i $ -th of the next $ m $ lines contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i, y_i \le n $ ) — the position of the $ i $ -th rook: $ x_i $ is the row and $ y_i $ is the column. No two rooks occupy the same cell. No two rooks attack each other.

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".

In the first testcase, the rooks are in the opposite corners of a $ 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 \times 3 $ board. It has $ 4 $ valid moves, and every move is fine because there's no other rook to attack it.