A. Трусливые ладьи
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана шахматная доска размера $$$n \times n$$$. На ней расположены $$$m$$$ ладей таким образом, что:

  • никакие две ладьи не занимают одну клетку;
  • никакие две ладьи не атакуют друг друга.

Ладья атакует все клетки, которые находятся в ее строке или столбце.

Можно ли подвинуть ровно одну ладью (вы можете самостоятельно выбрать, какую именно) в другую клетку так, что никакие две ладьи все еще не будут атаковать друг друга? Ладья может сходить в любую клетку в ее строке или столбце, если никакая другая ладья не стоит на ее пути.

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 2000$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 8$$$) — размер доски и количество ладей.

В $$$i$$$-й из следующих $$$m$$$ строк записаны два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$) — позиция $$$i$$$-й ладьи: $$$x_i$$$ — это строка, а $$$y_i$$$ — столбец.

Никакие две ладьи не занимают одну клетку. Никакие две ладьи не атакуют друг друга.

Выходные данные

На каждый набор входных данных выведите «YES», если можно подвинуть ровно одну ладью в другую клетку так, что никакие две ладьи все еще не будут атаковать друг друга. В противном случае выведите «NO».

Пример
Входные данные
2
2 2
1 2
2 1
3 1
2 2
Выходные данные
NO
YES
Примечание

В первом наборе входных данных ладьи стоят в противоположных углах доски $$$2 \times 2$$$. Каждая из них может сходить в соседний угол, но сходить туда означает попасть по атаку другой ладьи.

Во втором наборе входных данных одна ладья стоит в центре доски $$$3 \times 3$$$. У нее есть $$$4$$$ доступных хода, и каждый из них подходит, потому что нет другой ладьи, чтобы ее атаковать.