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


-----Examples-----

Input
2
2 2
1 2
2 1
3 1
2 2
Output
NO
YES


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

Source: codeforces | Difficulty: EASY
Tags: Implementation

Greedy algorithms


Solutions:
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')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = 0
	for i in range(m):
		(l, r) = map(int, input().split())
		if l != r:
			p += 1
	if m < n:
		print('YES')
	else:
		print('NO')


from sys import stdin

def readint():
	return int(stdin.readline())

def readarray(typ):
	return list(map(typ, stdin.readline().split()))

def readmatrix(n):
	M = []
	for _ in range(n):
		row = readarray(int)
		assert len(row) == n
		M.append(row)
	return M

def mult(M, v):
	n = len(M)
	return [sum((M[i][j] * v[j] for j in range(n))) for i in range(n)]
t = readint()
for _ in range(t):
	nm = readarray(int)
	n = nm[0]
	m = nm[1]
	for _ in range(m):
		rook_i = readarray(int)
	if m >= n:
		print('NO')
	else:
		print('YES')


t = int(input())
for v in range(t):
	b = input().split()
	p = [int(i) for i in b]
	for n in range(p[1]):
		input()
	if p[0] == p[1]:
		print('NO')
	else:
		print('YES')


desks_number = int(input())
answers = list((str() for answer_id in range(desks_number)))
rooks = list(([0, 0] for rook_id in range(8)))
for desk_id in range(desks_number):
	(desk_size, rooks_number) = tuple((int(value) for value in input().split()))
	for rook_id in range(rooks_number):
		(rooks[rook_id][0], rooks[rook_id][1]) = tuple((int(value) for value in input().split()))
	if desk_size > rooks_number:
		answers[desk_id] = 'YES'
	else:
		answers[desk_id] = 'NO'
for answer in answers:
	print(answer)


t = int(input())
out = ''
for _ in range(t):
	(n, m) = map(int, input().split())
	rooks = [tuple(map(int, input().split())) for __ in range(m)]
	if m < n:
		out += 'YES\n'
	else:
		out += 'NO\n'
print(out)


for _ in ' ' * int(input()):
	(a, b) = map(int, input().split())
	for i in range(b):
		z = input()
	if a == b:
		print('NO')
	else:
		print('YES')


for _ in ' ' * int(input()):
	(name, mam) = map(int, input().split())
	for _ in ' ' * mam:
		input()
	if name > mam:
		print('YES')
	else:
		print('NO')


n = int(input())
answer = []
ls = []
for i in range(n):
	(n, m) = map(int, input().split())
	for i in range(m):
		ls.append(input())
	if n == m:
		answer.append('NO')
	else:
		answer.append('YES')
for i in answer:
	print(i)


t = int(input())
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	count = m
	while m > 0:
		input()
		m -= 1
	if n - count == 0:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	a = input().split()
	if a[1] == 1:
		b = input()
		print('YES')
	else:
		for j in range(int(a[1])):
			b = input()
		if a[0] == a[1]:
			print('NO')
		else:
			print('YES')


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	for j in range(m):
		input()
	print('YNEOS'[m >= n::2])


t = int(input())
x = []
for i in range(t):
	s = input()
	s = s.split()
	n = int(s[0])
	m = int(s[1])
	for j in range(m):
		s = input()
	if n > m:
		x.append('YES')
	else:
		x.append('NO')
for i in range(t):
	print(x[i])


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


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	rows = [False] * n
	columns = [False] * n
	for _ in range(m):
		(x, y) = map(int, input().split())
		rows[y - 1] = True
		columns[x - 1] = True
	for i in range(n):
		if not rows[i] or not columns[i]:
			print('YES')
			break
	else:
		print('NO')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(m):
		(x, y) = map(int, input().split())
		a.append([x, y])
	if m < n:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split())
	(row, col) = ([0] * n, [0] * n)
	for i in range(m):
		(x, y) = map(int, input().split())
		row[x - 1] += 1
		col[y - 1] += 1
	cnt1 = cnt2 = 0
	for i in range(n):
		if row[i] == 0:
			cnt1 += 1
		if col[i] == 0:
			cnt2 += 1
	return 'YES' if min(cnt1, cnt2) > 0 else 'NO'
for _ in range(int(input())):
	print(solve())


t = int(input())

def solve():
	(n, k) = map(int, input().split())
	m = k
	while m:
		input()
		m -= 1
	if k < n:
		print('YES')
	else:
		print('NO')
while t:
	solve()
	t -= 1


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


import sys
import math

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_ls():
	return list(map(int, sys.stdin.readline().strip().split()))

def yesno(ok):
	print('YES' if ok else 'NO')

def main():
	for _ in range(int(input())):
		(n, m) = get_ints()
		pos = []
		for i in range(m):
			(x, y) = get_ints()
			pos.append([x, y])
		if m >= n:
			print('NO')
		else:
			print('YES')
main()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	list1 = []
	list2 = []
	for i in range(1, n + 1):
		list1.append(i)
		list2.append(i)
	for i in range(m):
		(x, y) = map(int, input().split())
		list1.remove(x)
		list2.remove(y)
	if len(list1) > 0 and len(list2) > 0:
		print('YES')
	else:
		print('NO')


def sol():
	m = int(input())
	for i in range(m):
		(n, z) = map(int, input().split(' '))
		lx = []
		ly = []
		for j in range(n):
			lx.append(j + 1)
			ly.append(j + 1)
		for k in range(z):
			(a, b) = map(int, input().split(' '))
			lx.remove(a)
			ly.remove(b)
		if lx == [] or ly == []:
			print('NO')
		else:
			print('YES')
sol()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	rooks = list([tuple(map(int, input().split())) for i in range(m)])
	print('NO' if n == m else 'YES')


def solution():
	(n, m) = (int(num) for num in input().split())
	for i in range(m):
		input()
	if m < n:
		print('YES')
	else:
		print('NO')

def main():
	t = int(input())
	while t:
		solution()
		t -= 1
main()


t = int(input())
for iter in range(t):
	line1 = input().split(' ')
	n = int(line1[0])
	m = int(line1[1])
	for j in range(m):
		input()
	if m < n:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	x_i = []
	y_i = []
	for _ in range(m):
		(x, y) = map(int, input().split())
		x_i.append(x)
		y_i.append(y)
	if len(set(x_i)) < n and len(set(y_i)) < n:
		print('YES')
	else:
		print('NO')


def test_case():
	(n, rooks) = map(int, input().split(' '))
	for _ in range(rooks):
		input()
	if rooks < n:
		print('YES')
	else:
		print('NO')
test_cases = int(input())
for _ in range(test_cases):
	test_case()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(row, col) = ([1] * n, [1] * n)
	for i in range(m):
		(x, y) = map(int, input().split())
		row[x - 1] = 0
		col[y - 1] = 0
	if sum(row) > 0 or sum(col) > 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a0 = [0] * n
	b0 = [0] * n
	for j in range(m):
		(a, b) = map(int, input().split())
		a0[a - 1] = 1
		b0[b - 1] = 1
	if 0 not in a0 and 0 not in b0:
		print('NO')
	else:
		print('YES')


def solve():
	(n, m) = map(int, input().split())
	a = []
	(r, c) = ([], [])
	(rr, cc) = ([], [])
	for i in range(1, n + 1):
		r.append(i)
		c.append(i)
	for i in range(0, m):
		(x, y) = list(map(int, input().split()))
		a.append([x, y])
		rr.append(x)
		cc.append(y)
	ans1 = set(r) - set(rr)
	ans2 = set(c) - set(cc)
	if ans1 and ans2:
		return 'YES'
	else:
		return 'NO'
for t in range(0, int(input())):
	print(solve())


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(m):
		l1 = list(map(int, input().split()))
		l.append(l1)
	if n > m:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	for _ in range(m):
		(x, y) = map(int, input().split())
	if n == m:
		print('NO')
	elif m == 1:
		print('YES')
	elif n == 1 and m == 1:
		print('YES')
	elif n == 1 and m > 1:
		print('NO')
	elif n - m >= 1:
		print('YES')


n = int(input())
for i in range(n):
	r = [int(x) for x in input().split()]
	for j in range(r[1]):
		x = input()
	if r[0] > r[1]:
		print('YES')
	else:
		print('NO')


t = int(input())
result = ''
while t:
	t -= 1
	(n, m) = map(int, input().split())
	rows = []
	cols = []
	for i in range(m):
		(x, y) = map(int, input().split())
		rows.append(x)
		cols.append(y)
	result += 'YES' if len(cols) < n or len(rows) < n else 'NO'
	result += '\n'
print(result[:-1])


for i in range(int(input())):
	(n, m) = map(int, input().split())
	for j in range(m):
		(a, b) = map(int, input().split())
	if m == n:
		print('NO')
	else:
		print('YES')


from collections import defaultdict as maps
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	rows = maps(int)
	cols = maps(int)
	for __ in range(m):
		(x, y) = map(int, input().split())
		rows[x] += 1
		cols[y] += 1
		flag = 0
	for i in range(1, n + 1):
		if rows[i] == 0 or cols[i] == 0:
			flag = 1
			break
	print('YES') if flag else print('NO')


def main():
	(n, m) = map(int, input().split(' '))
	d = {i: 0 for i in range(1, m + 1)}
	for i in range(1, m + 1):
		(x, y) = map(int, input().split(' '))
		d[x] = 1
		d[y] = 1
	if m >= n:
		print('NO')
	else:
		print('YES')
t = int(input())
for i in range(t):
	main()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for _ in range(m):
		l += list(map(int, input().split()))
	if n == m:
		print('NO')
	else:
		print('YES')


from math import gcd

def printList(l):
	for i in l:
		print(i, end=' ')
	print()
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	loc = []
	count = 0
	for i in range(m):
		(x, y) = map(int, input().split())
	if n > m:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	for x in range(q):
		k = str(input())
	if n > q:
		print('YES')
	else:
		print('NO')


def solution(t):
	for __ in range(0, t):
		(n, m) = map(int, input().split())
		rooks = []
		for i in range(0, m):
			rooks.append(input())
		if n > m:
			print('YES')
		else:
			print('NO')

def main():
	test_cases = int(input())
	solution(test_cases)
main()


t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	p = m
	while p:
		p -= 1
		(a, b) = map(int, input().split())
	if n <= m:
		print('NO')
		continue
	else:
		print('YES')


cases = int(input())
for case in range(1, cases + 1):
	(n, m) = [int(i) for i in input().split()]
	rooks = []
	for _ in range(m):
		input()
	print(('NO', 'YES')[m < n])


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	for i in range(m):
		(a, b) = map(int, input().split())
	if n > m:
		print('YES')
	else:
		print('NO')
	t -= 1


t = int(input())
for i in range(t):
	x = input()
	n = int(x[0])
	m = int(x[2])
	for j in range(m):
		y = input()
	if m < n:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(x, y) = map(int, input().split())
	for i in range(y):
		c = input()
	if x == y:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	L = []
	for i in range(m):
		(xi, yi) = map(int, input().split())
		L.append([xi, yi])
	if n == 1:
		print('NO')
	elif m == 1:
		print('YES')
	elif n == 2:
		print('NO')
	elif n == m:
		print('NO')
	elif m == n - 1:
		print('YES')
	else:
		print('YES')


t = int(input())
l = []
for i in range(t):
	l1 = input().split(' ')
	for i in range(int(l1[1])):
		l2 = input().split()
	if int(l1[0]) == int(l1[1]):
		print('NO')
	else:
		print('YES')


n = int(input())
result = []
for i in range(n):
	(m, x) = map(int, input().split(' '))
	for i in range(x):
		input()
	if x >= m:
		result.append('NO')
	else:
		result.append('YES')
for i in range(n):
	print(result[i])


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	rows = [0 for i in range(n)]
	cols = [0 for i in range(n)]
	for _ in range(m):
		(x, y) = map(int, input().split())
		rows[x - 1] = 1
		cols[y - 1] = 1
		f = False
	for a in rows:
		if a == 0:
			print('YES')
			f = True
			break
	if not f:
		for b in cols:
			if b == 0:
				print('YES')
				f = True
				break
	if not f:
		print('NO')
	t -= 1


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	t = r
	while t:
		(a, b) = map(int, input().split())
		t -= 1
	if r == n:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l1 = []
	l2 = []
	for i in range(m):
		(a, b) = map(int, input().split())
		l1.append(a)
		l2.append(b)
	c = 0
	d = 0
	for i in range(1, n + 1):
		if i not in l1:
			c = i
		if i not in l1:
			d = i
	if c != 0 and d != 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = []
	k = []
	for j in range(b):
		(c, d) = map(int, input().split())
		if c not in l:
			l.append(c)
		if d not in k:
			k.append(d)
	if len(l) <= a - 1 and len(k) <= a - 1:
		print('YES')
	else:
		print('NO')


def fxn(list1, list2):
	if list1 == [1] * len(list1) or list2 == [1] * len(list2):
		return 'NO'
	else:
		return 'YES'
t = int(input())
for i in range(t):
	a = list(map(int, input().split()))
	listx = [0] * a[0]
	listy = [0] * a[0]
	for j in range(a[1]):
		k = list(map(int, input().split()))
		listx[k[0] - 1] = 1
		listy[k[1] - 1] = 1
	print(fxn(listx, listy))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	r = m
	while r > 0:
		(x, y) = map(int, input().split())
		r = r - 1
	if m == 1 and n > m:
		print('YES')
	elif n == m:
		print('NO')
	else:
		print('YES')


nousecount = int(input())
for nouse in range(nousecount):
	(n, m) = map(int, input().split(' '))
	for i in range(m):
		s = input()
	if m < n:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, m) = input().split()
	list = []
	for i in range(1, int(n) + 1):
		list.append(i)
	pos = []
	xp = []
	yp = []
	for _ in range(int(m)):
		pos.append(input().split())
	for p in pos:
		xp.append(int(p[0]))
		yp.append(int(p[1]))
	check = True
	for l in list:
		if not l in xp:
			for l in list:
				if not l in yp:
					check = False
					print('YES')
					break
		if not check:
			break
	if check:
		print('NO')


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


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = []
	for _ in range(m):
		(c, d) = map(int, input().split())
		s.append([c, d])
	if n > m:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	pos = []
	for i in range(m):
		x = input().split()
		pos.append(x)
	if m >= n:
		print('NO')
	else:
		print('YES')
	t -= 1


def Cowardly_Rooks(numberofrooks):
	for i in range(numberofrooks):
		(rook1, rook2) = map(int, input().split())
		list2 = []
		for i in range(rook2):
			(pos1, pos2) = map(int, input().split())
			list2.append(pos1)
			list2.append(pos2)
		if rook1 > rook2:
			print('YES')
		else:
			print('NO')
numberofrooks = int(input())
Cowardly_Rooks(numberofrooks)


t = int(input())
for z in range(t):
	lis = []
	(n, m) = [int(x) for x in input().split(' ', 1)]
	for i in range(m):
		lis.append([int(x) for x in input().split(' ', 1)])
	if m < n:
		print('YES')
	else:
		print('NO')


import math

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def inchar():
	return list(input().split())

def insr():
	s = input()
	return list(s)

def invr():
	return map(int, input().split())
a = inp()
for _ in range(a):
	k = inlt()
	for _ in range(k[1]):
		_ = inlt()
	if k[0] != k[1]:
		print('YES')
	else:
		print('NO')


no_testcases = int(input())
for j in range(no_testcases):
	nm = list(map(int, input().split(' ')))
	n = nm[0]
	m = nm[1]
	positions = []
	row_pos = []
	column_pos = []
	for i in range(m):
		a = list(map(int, input().split(' ')))
		row_pos.append(a[0])
	if n == m:
		print('NO')
	else:
		print('YES')


a = int(input())
sp = []
for i in range(a):
	o = []
	li = 0
	(x, y) = map(int, input().split())
	s1 = []
	s2 = []
	for t in range(y):
		(stroka, stolb) = map(int, input().split())
	if y < x:
		sp.append('YES')
	else:
		sp.append('NO')
for i in sp:
	print(i)


cases = int(input())
A = []
for i in range(cases):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	for j in range(m):
		(x, y) = input().split()
	if m < n:
		A.append('YES')
	else:
		A.append('NO')
for k in range(cases):
	print(A[k])


resul = []

def check(arg):
	b = arg[1]
	for l in range(b):
		posi = input()
		posi = posi.split()
		for i in range(len(posi)):
			posi[i] = int(posi[i])
	if arg[0] > arg[1]:
		resul.append('YES')
	else:
		resul.append('NO')

def main():
	tot = int(input())
	for j in range(tot):
		sizRook = input()
		sizRook = sizRook.split()
		for i in range(len(sizRook)):
			sizRook[i] = int(sizRook[i])
		check(sizRook)
	for k in range(len(resul)):
		print(resul[k])
main()


Line1 = int(input().rstrip())
testCases = []
boards = [[] for _ in range(Line1)]
for i in range(Line1):
	nm = list(map(int, input().rstrip().split(' ')))
	(n, m) = (nm[0], nm[1])
	if n == m:
		print('NO')
	else:
		print('YES')
	for j in range(m):
		boards[i].append(list(map(int, input().rstrip().split(' '))))


import math
import collections
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	matrix = [input().split() for i in range(m)]
	if n > m:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	c = list(range(1, n + 1))
	d = list(range(1, n + 1))
	for j in range(m):
		z = list(map(int, input().split()))
		c.remove(z[0])
		d.remove(z[1])
	if len(c) >= 1 and len(d) >= 1:
		print('YES')
	else:
		print('NO')


loop_num = int(input())
for i in range(loop_num):
	(n, m) = map(int, input().split())
	for i in range(1, m + 1):
		(x, y) = map(int, input().split())
	if m < n:
		print('YES')
	else:
		print('NO')


t = int(input())
result = []
if t <= 2000 and t >= 1:
	for i in range(t):
		lis = []
		num = input().split()
		for i in num:
			if int(i) <= 8 and int(i) >= 1:
				lis.append(int(i))
		for n in range(lis[1]):
			l = input().split()
		if lis[0] > lis[1]:
			result.append('YES')
		else:
			result.append('NO')
for i in result:
	print(i)


t = int(input())
j = []
for c in range(t):
	if 1 <= t <= 2000:
		(n, m) = map(int, input().split())
		if 1 <= m <= 8 and 1 <= n <= 8:
			board = n * n
			rc = []
			for g in range(m):
				(row, culmn) = map(int, input().split())
				if 1 <= row <= n and 1 <= culmn <= n:
					rc.append(row)
					rc.append(culmn)
				else:
					break
			if m >= n:
				j.append('NO')
			else:
				j.append('YES')
		else:
			break
for t in j:
	print(t)


h = int(input())
for i in range(h):
	k = str(input())
	k1 = k.split(' ')
	n = int(k1[0])
	m = int(k1[1])
	A = [[1 for i in range(n)] for j in range(n)]
	B = []
	D = {'YES': 0}
	for j in range(m):
		k2 = str(input())
	if m < n:
		print('YES')
	else:
		print('NO')


YN = []
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	for j in range(m):
		(x, y) = map(int, input().split())
	if n > m:
		YN.append(1)
	else:
		YN.append(0)
for i in YN:
	if i == 1:
		print('YES')
	else:
		print('NO')


def solution():
	t = int(input())
	for _ in range(t):
		(n, m) = list(map(int, input().split()))
		a = [[0 for _ in range(m)] for _ in range(n)]
		for i in range(m):
			(p, q) = list(map(int, input().split()))
			a.append((p, q))
		if n > m:
			print('YES')
		else:
			print('NO')
solution()


(t, r) = (int(input()), [])
for _ in range(t):
	s = input().split()
	(n, m) = (int(s[0]), int(s[1]))
	p = [input() for _ in range(m)]
	if m < n:
		r.append('YES')
	else:
		r.append('NO')
print(*r, sep='\n')


def fun(arr, n, m):
	if m >= n:
		return False
	if n > m:
		return True
	else:
		flag1 = True
		flag2 = True
		for i in arr:
			if i[0] != i[1]:
				flag1 = False
				break
		for i in arr:
			if i[0] + i[1] != n + 1:
				flag2 = False
				break
		if flag1 == False and flag2 == False:
			return True
	return False
t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	arr = []
	for i in range(m):
		arr.append(list(map(int, input().split())))
	if fun(arr, n, m):
		print('YES')
	else:
		print('NO')
	t = t - 1


for t in range(int(input())):
	(n, m) = map(int, input().split())
	for x in range(m):
		(a, b) = map(int, input().split())
	print('NO' if m >= n else 'YES')


t = int(input())
for tc in range(t):
	(n, m) = [int(x) for x in input().split(' ')]
	for i in range(m):
		ipt = input()
	if m < n:
		print('YES')
	else:
		print('NO')