Cowardly Rooks (Codeforces 1749A)
Tags: Greedy, implementation

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.

Input: 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.

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

Note: 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.

Sample Inputs:
2
2 2
1 2
2 1
3 1
2 2

Sample Outputs:
NO
YES

Solution (Python):
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    for _ in range(m):
        input()
    print('NO' if n == m else 'YES')

Solution (Python):
for _ in range(int(input())):
    (n, m) = map(int, input().split(' '))
    for i in range(m):
        input()
    if m < n:
        print('YES')
    else:
        print('NO')

Solution (Python):
for tc in range(int(input())):
    (n, m) = map(int, input().split())
    for i in range(m):
        input()
    print('YES' if n > m else 'NO')