Read problem statements in [Mandarin], [Bengali], and [Russian] as well.

You are given a positive integer N. Consider a square grid of size N \times N, with rows numbered  1 to N from top to bottom and columns numbered 1 to N from left to right. Initially you are at (1,1) and you have to reach (N,N). From a cell you can either move one cell to the right or one cell down (if possible). Formally, if you are at (i,j), then you can either move to (i+1,j) if i < N, or to (i,j+1) if j < N.

There are exactly N blocks in the grid, such that each row contains exactly one block and each column contains exactly one block. You can't move to a cell which contains a block. It is guaranteed that blocks will not placed in (1,1) and (N,N).

You have to find out whether you can reach (N,N).

------ Input Format ------ 

- The first line contains T - the number of test cases. Then the test cases follow.
- The first line of each test case contains N - the size of the square grid.
- The i-th line of the next N lines contains two integers X_{i} and Y_{i} indicating that (X_{i}, Y_{i}) is the position of a block in the grid.

------ Output Format ------ 

For each test case, if there exists a path from (1,1) to (N,N), output YES, otherwise output NO.

You may print each character of the string in uppercase or lowercase (for example, the strings yEs, yes, Yes and YES will all be treated as identical).

------ Constraints ------ 

$1 ≤T ≤1000$
$2 ≤N ≤10^{6}$
$1 ≤X_{i},Y_{i} ≤N$
$(X_{i}, Y_{i}) \ne (1, 1)$ and $(X_{i}, Y_{i}) \ne (N, N)$ for all $1 ≤i ≤N$
$X_{i} \ne X_{j}$ and $Y_{i} \ne Y_{j}$ for all $1 ≤i < j ≤N$
- Sum of $N$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
2
3
1 2
2 3
3 1
2
1 2
2 1
----- Sample Output 1 ------ 
YES
NO
----- explanation 1 ------ 
- Test case $1$: We can follow the path $(1,1) \to (2,1) \to (2,2) \to (3,2) \to (3,3)$.

- Test case $2$: We can't move from the starting point, so it is impossible to reach $(N, N)$.

Source: codechef | Difficulty: HARD
Tags: Sorting

Data structures


Solutions:
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	c = dict()
	for i in range(n):
		(a, b) = map(int, input().split())
		if a + b in c:
			c[a + b] += 1
		else:
			c[a + b] = 1
	fl = 1
	for i in range(2, n + 1):
		if i in c:
			if c[i] == i - 1:
				fl = 0
				break
	j = n + 1
	k = n
	for i in range(n - 1):
		if j in c:
			if c[j] == k:
				fl = 0
				break
		j += 1
		k -= 1
	if fl == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	obs = []
	for _ in range(n):
		obs.append(tuple(map(int, input().split())))
	obs.sort()
	ans = 'YES'
	check = False
	for i in range(1, n):
		if obs[i - 1][0] == 1 or obs[i - 1][1] == n:
			check = True
		if check:
			if obs[i - 1][1] - obs[i][1] != 1:
				check = False
		if (obs[i][0] == n or obs[i][1] == 1) and check:
			ans = 'NO'
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = []
	dic = {}
	a = []
	for i in range(n):
		l1 = list(map(int, input().split()))
		dic[l1[0]] = l1[1]
		if l1[1] == 1:
			a = l1
	fl = 1
	for i in range(a[0]):
		if dic[a[0] - i] != i + 1:
			fl = 0
			break
	if fl == 1:
		print('NO')
		continue
	fl = 1
	for i in range(n - dic[n] + 1):
		if dic[n - i] != dic[n] + i:
			fl = 0
			break
	if fl == 1:
		print('NO')
		continue
	else:
		print('YES')


def sol(n, blocks):
	blocks.sort()
	top_left = -1
	for i in range(1, n):
		if blocks[i][1] == blocks[i - 1][1] - 1:
			top_left = i
		else:
			break
	bottom_right = -1
	for i in range(n - 2, -1, -1):
		if blocks[i][1] == blocks[i + 1][1] + 1:
			bottom_right = i
		else:
			break
	if top_left != -1 and blocks[top_left][1] == 1 or (bottom_right != -1 and blocks[bottom_right][1] == n):
		return 'NO'
	else:
		return 'YES'
t = int(input())
while t > 0:
	n = int(input())
	blocks = []
	for i in range(n):
		temp = list(map(int, input().split()))
		blocks.append(temp)
	print(sol(n, blocks))
	t = t - 1


from sys import stdin, stdout
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	dict_ = {}
	for _ in range(n):
		(a, b) = [int(i) for i in stdin.readline().split()]
		dict_[a] = b
	prev = (1, dict_[1] - 1)
	flag = 0
	for i in range(2, n + 1):
		(a, b) = prev
		prev_diff = b - a + 1
		col = dict_[i]
		if prev_diff == 1 and col == a:
			flag = 1
			break
		if b <= col:
			new = (1, col - 1)
		elif a < col < b:
			new = (1, n)
		else:
			new = (col + 1, n)
		prev = new
	if flag == 1:
		print('NO')
	elif prev[1] == n:
		print('YES')
	else:
		print('NO')


from itertools import permutations as per
from math import factorial as fact
from difflib import SequenceMatcher
t = int(input())
for _ in range(t):
	n = int(input())
	d = {}
	for i in range(n):
		(x, y) = map(int, input().split())
		if x + y in d.keys():
			d[x + y] += 1
		else:
			d[x + y] = 1
	for (k, v) in d.items():
		if k > n + 1:
			k = 2 * n + 2 - k
		if k - 1 == v:
			print('NO')
			break
	else:
		print('YES')


import sys

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

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

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')
from sys import maxsize

def subHelper(data, n, ind):
	x = data[ind][0]
	y = data[ind][1]
	if x == 1:
		req = y - 1
	else:
		req = n - x
	ind += 1
	while req > 0 and ind < n:
		if data[ind][0] == x + 1 and data[ind][1] == y - 1:
			req -= 1
			x = data[ind][0]
			y = data[ind][1]
			ind += 1
		else:
			return False
	if req == 0:
		return True
	return False

def helper(data, n):
	for i in range(n):
		if data[i][0] == 1 or data[i][1] == n:
			if subHelper(data, n, i):
				return True
	return False

def solve():
	for _ in range(get_int()):
		n = get_int()
		data = []
		for i in range(n):
			data.append(get_list())
		data.sort()
		if helper(data, n):
			get_print('NO')
		else:
			get_print('YES')
solve()


for _ in range(int(input())):
	n = int(input())
	li = sorted([list(map(int, input().split())) for i in range(n)])
	k = li[0][0] + li[0][1]
	for i in range(n):
		if sum(li[i]) != k:
			break
		a = li[i][1]
	k = sum(li[n - 1])
	for i in reversed(range(n)):
		if sum(li[i]) != k:
			break
		b = li[i][1]
	print('NO') if a == 1 or b == n else print('YES')


for _ in range(int(input())):
	n = int(input())
	li = []
	for i in range(n):
		(p, q) = map(int, input().split())
		li.append([p, q])
	li.sort()
	k = li[0][0] + li[0][1]
	for i in range(n):
		if sum(li[i]) != k:
			break
		a = li[i][1]
	k = sum(li[n - 1])
	for i in range(n - 1, -1, -1):
		if sum(li[i]) != k:
			break
		b = li[i][1]
	if a == 1 or b == n:
		print('NO')
	else:
		print('YES')


from sys import stdin

def solve():
	for _ in range(int(stdin.readline().strip())):
		N = int(stdin.readline().rstrip())
		Y = [0] * N
		for _ in range(N):
			(x, y) = map(int, stdin.readline().rstrip().split())
			Y[x - 1] = y
		pos = 1
		ranges = [(1, Y[0])]
		_pass = 0
		for y in Y[1:]:
			if _pass:
				continue
			if y > pos:
				if y < N and ranges[0][1] - 1 > y:
					ranges = [(pos, y), (y + 1, N + 1)]
				else:
					tmp = 0
					if ranges[-1][1] - 1 > y:
						tmp = (max(ranges[-1][0], y + 1), N + 1)
					ranges = [(pos, y)]
					if tmp:
						ranges.append(tmp)
			elif y < pos:
				continue
			elif y < ranges[0][1] - 1:
				ranges = [(max(y + 1, ranges[0][0]), N + 1)]
				pos = ranges[0][0]
			elif y < ranges[-1][1] - 1:
				ranges = [(max(y + 1, ranges[-1][0]), N + 1)]
				pos = ranges[0][0]
			else:
				found = 0
				for (i, j) in ranges:
					if y + 1 in range(i, j):
						pos = y + 1
						ranges = [(pos, N + 1)]
						found = 1
						break
				if not found:
					_pass = 1
					continue
		ans = 'NO'
		if not _pass:
			for (i, j) in ranges:
				if N in range(i, j):
					ans = 'YES'
		print(ans)
solve()


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = defaultdict(list)
	flag = 1
	for i in range(n):
		(l, k) = map(int, input().split())
		if l + k in arr:
			arr[l + k] += 1
		else:
			arr[l + k] = 1
	for i in arr:
		if i < n + 1:
			if i - 1 == arr[i]:
				flag = 0
				break
		elif 2 * n - i + 1 == arr[i]:
			flag = 0
			break
	print('YES') if flag else print('NO')


t = int(input())
for z in range(t):
	n = int(input())
	points = []
	for i in range(n):
		points.append(list(map(int, input().split())))
	points.sort(key=lambda x: x[0])
	flag = True
	seq = []
	seq_start = 0
	for i in range(1, n):
		if flag and points[i][1] - points[i - 1][1] == -1 and (points[i][0] - points[i - 1][0] == 1):
			continue
		if flag:
			seq.append([seq_start, i - 1])
			seq_start = i
	seq.append([seq_start, n - 1])
	for sequence in seq:
		if points[sequence[0]][0] + points[sequence[1]][1] == 2:
			break
		if points[sequence[0]][1] + points[sequence[1]][0] == 2 * n:
			break
	else:
		print('YES')
		continue
	print('NO')


for _ in range(int(input())):
	n = int(input())
	d = {}
	for i in range(n):
		(x, y) = map(int, input().split())
		val = y - 1
		if x + val <= n:
			if d.get(x + val) is None:
				d[x + val] = 1
			else:
				d[x + val] += 1
		else:
			val = y - (n - x)
			if d.get(n + val - 1) is None:
				d[n + val - 1] = 1
			else:
				d[n + val - 1] += 1
	flag = True
	for i in range(2, n + 1):
		if d.get(i) is not None and d[i] == i:
			flag = False
			break
	k = n - 1
	for i in range(n + 1, n + n - 1):
		if d.get(i) is not None and d[i] == k:
			flag = False
			break
		k -= 1
	if flag:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	d = {}
	a = []
	for i in range(n):
		(x, y) = map(int, input().split())
		a.append([x, y])
	a.sort(key=lambda x: -x[1])
	i = 0
	reach = False
	while i < n:
		if a[i][0] == 1 or a[i][1] == n:
			j = i + 1
			x = a[i][0]
			y = a[i][1]
			while j < n:
				x += 1
				y -= 1
				if a[j][0] == x and a[j][1] == y:
					pass
				else:
					break
				if a[j][0] == n or a[j][1] == 1:
					reach = True
				j += 1
			if reach:
				break
			i = j
		i += 1
	if reach:
		print('NO')
	else:
		print('YES')


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	blocks = []
	for i in range(n):
		(x, y) = map(int, input().split())
		blocks.append([x, y])
	blocks.sort()
	TopLeft = -1
	BottomRight = -1
	for i in range(1, n):
		if blocks[i][1] == blocks[i - 1][1] - 1:
			TopLeft = i
		else:
			break
	for i in range(n - 2, -1, -1):
		if blocks[i][1] == blocks[i + 1][1] + 1:
			BottomRight = i
		else:
			break
	if TopLeft != -1 and blocks[TopLeft][1] == 1 or (BottomRight != -1 and blocks[BottomRight][1] == n):
		print('NO')
	else:
		print('YES')


def solve(arr):
	arr.sort(key=lambda x: x[0])
	TopTOLeft = -1
	BottomToRight = -1
	for i in range(1, len(arr)):
		if arr[i][1] == arr[i - 1][1] - 1:
			TopTOLeft = i
		else:
			break
	for i in range(len(arr) - 2, -1, -1):
		if arr[i][1] == arr[i + 1][1] + 1:
			BottomToRight = i
		else:
			break
	if TopTOLeft != -1 and arr[TopTOLeft][1] == 1 or (BottomToRight != -1 and arr[BottomToRight][1] == len(arr)):
		print('NO')
	else:
		print('YES')

def main():
	for i in range(int(input())):
		arr = []
		n = int(input())
		for i in range(n):
			a = list(map(int, input().split()))
			arr.append(a)
		solve(arr)
main()


for i in range(int(input())):
	n = int(input())
	dict = {}
	for i in range(2, n + n + 1):
		dict[i] = 0
	for i in range(n):
		(j, k) = map(int, input().split())
		dict[j + k] = dict[j + k] + 1
	flag = 1
	for i in range(2, n + 2):
		if dict[i] >= i - 1:
			flag = 0
	x = n - 1
	for i in range(n + 2, n + n + 1):
		if dict[i] >= x:
			flag = 0
		x = x - 1
	if flag == 0:
		print('NO')
	else:
		print('YES')


def sol(d, n):
	i = 1
	while d[i] == d[i + 1] + 1:
		i += 1
		if i == n:
			break
	if d[i] == 1:
		return 'NO'
	i = n
	while d[i] == d[i - 1] - 1:
		i -= 1
		if i == 1:
			break
	if d[i] == n:
		return 'NO'
	return 'YES'
for _ in range(int(input())):
	n = int(input())
	d = {}
	for i in range(n):
		(X, Y) = map(int, input().split())
		d[Y] = X
	print(sol(d, n))


def process(N, blocks):
	flag = True
	for i in range(3, N + 2):
		if i in blocks and blocks[i] == i - 1:
			return 'NO'
	k = N - 1
	for i in range(2 + N, 2 * N):
		if i in blocks and blocks[i] == k:
			return 'NO'
		k -= 1
	return 'YES'
for _ in range(int(input())):
	N = int(input())
	blocks = {}
	for __ in range(N):
		(x, y) = map(int, input().split())
		if x + y in blocks:
			blocks[x + y] += 1
		else:
			blocks[x + y] = 1
	print('NO' if N == 2 else process(N, blocks))


for _ in range(int(input())):
	n = int(input())
	xd = [0] * (2 * n)
	for _ in range(n):
		(x, y) = map(int, input().split())
		xd[x + y] += 1
	ans = 'YES'
	for i in range(3, n + 2):
		if xd[i] == i - 1:
			ans = 'NO'
			break
	if ans == 'YES':
		s = n - 1
		for i in range(n + 2, 2 * n):
			if xd[i] == s:
				ans = 'NO'
				break
			s -= 1
	print(ans)


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
H = 1000000000 + 7
for _ in range(I()):
	n = I()
	d = {}
	p = []
	for i in range(n):
		(a, b) = M()
		d[a, b] = 1
		p.append((a, b))
	p.sort(key=lambda x: x[1])
	f1 = f2 = 1
	(i, j) = (p[0][0], p[0][1])
	t = 0
	while t < n and 1 <= j <= n and (1 <= i <= n):
		if p[t][0] != i or p[t][1] != j:
			f1 = 0
			break
		else:
			t += 1
		i -= 1
		j += 1
	(i, j) = (p[-1][0], p[-1][1])
	t = n - 1
	while t >= 0 and 1 <= j <= n and (1 <= i <= n):
		if p[t][0] != i or p[t][1] != j:
			f2 = 0
			break
		else:
			t -= 1
		i += 1
		j -= 1
	if f1 == f2 == 0:
		print('YES')
	else:
		print('NO')


from sys import stdin
for i in range(int(stdin.readline())):
	n = int(stdin.readline())
	h = {}
	for j in range(n):
		(x, y) = map(int, stdin.readline().split())
		if x + y not in h:
			h[x + y] = 1
		else:
			h[x + y] += 1
	flag = 1
	for g in h.keys():
		if g <= n + 1 and h[g] == g - 1:
			flag = 0
		if g > n + 1 and h[g] == 2 * n + 1 - g:
			flag = 0
	if flag == 0:
		print('NO')
	else:
		print('YES')


for t in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		(x, y) = map(int, input().split())
		b = [x, y]
		a.append(b)
	a.sort()
	x = -(10 ** 9 + 7)
	for i in range(1, n):
		if a[i][1] == a[i - 1][1] - 1:
			x = i
		else:
			break
	y = -(10 ** 9 + 7)
	for i in range(n - 2, -1, -1):
		if a[i][1] == a[i + 1][1] + 1:
			y = i
		else:
			break
	if 0 <= x and x < n and (a[x][1] == 1) or (0 <= y and y < n and (a[y][1] == n)):
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	for __ in range(n):
		(x, y) = map(int, input().split())
		a.append([x, y])
	a.sort()
	row = 1
	col = n
	d = {}
	for i in range(n):
		num = a[i][1] - col
		if num not in d:
			d[num] = 0
		d[num] += 1
		row += 1
		col -= 1
	ans = 1
	for (k, v) in d.items():
		if abs(k) + v == n:
			ans = 0
	if ans:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	obs = {}
	for _ in range(n):
		(x, y) = input().split()
		(x, y) = (int(x), int(y))
		if x + y - 2 in obs:
			obs[x + y - 2] += 1
		else:
			obs[x + y - 2] = 1
	for i in obs.keys():
		if i <= n - 1:
			if obs[i] == i + 1:
				print('NO')
				break
		if i > n - 1:
			if obs[i] == n - 1 - (i - n):
				print('NO')
				break
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	for i in range(n):
		(x, y) = map(int, input().split())
		arr.append((x, y))
	arr.sort()
	flag1 = False
	for i in range(n):
		if arr[i][0] == 1 or arr[i][1] == n:
			x = arr[i][0]
			y = arr[i][1]
			k = i + 1
			flag2 = False
			for j in range(arr[i][1] - arr[i][0]):
				if arr[k] == (x + 1, y - 1):
					x += 1
					y -= 1
					k += 1
					continue
				else:
					flag2 = True
					break
			if flag2 == False:
				flag1 = True
				break
	if flag1 == False:
		print('YES')
	else:
		print('NO')


import sys
from collections import defaultdict
ins = lambda : sys.stdin.readline().strip()
inarr = lambda s: list(map(s, sys.stdin.readline().strip().split()))
outs = lambda n: sys.stdout.write(str(n) + '\n')
outarr = lambda li: sys.stdout.write(' '.join(map(str, li)) + '\n')
gcd = lambda a, b: b if a == 0 else gcd(b % a, a)

def solve():
	n = int(ins())
	d = defaultdict(int)
	for __ in range(n):
		(x, y) = inarr(int)
		d[x + y] += 1
	for i in range(2, n + 1):
		if d[i] == i - 1:
			outs('NO')
			return
	diagonal_size = n
	for i in range(n + 1, 2 * n):
		if d[i] == diagonal_size:
			print('NO')
			return
		diagonal_size -= 1
	outs('YES')
t = int(ins())
for _ in range(t):
	solve()


for t in range(int(input())):
	N = int(input())
	arr = [tuple(map(int, input().split())) for i in range(N)]
	mp = {}
	flag = False
	for (i, j) in arr:
		if i + j in mp:
			mp[i + j] += 1
		else:
			mp[i + j] = 1
		if i + j > N + 1:
			if mp[i + j] == 2 * N - i - j + 1:
				flag = True
				break
		elif mp[i + j] == i + j - 1:
			flag = True
			break
	if flag:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	arr = []
	bound = []
	ans = 0
	for q in range(n):
		(a, b) = map(int, input().split())
		arr.append([a - 1, b - 1])
		if a == 1 or b == 1 or a == n or (b == n):
			bound.append([a - 1, b - 1])
	i = 0
	if n == 2:
		if [0, 1] in bound and [1, 0] in bound:
			print('NO')
		else:
			print('YES')
	elif [1, 0] in bound and [0, 1] in bound or ([n - 1, n - 2] in bound and [n - 2, n - 1] in bound):
		print('NO')
	else:
		arr = sorted(arr)
		while i + 1 < len(arr):
			x = arr[i][0]
			y = arr[i][1]
			nx = arr[i + 1][0]
			ny = arr[i + 1][1]
			if nx == 1 + x and ny + 1 == y:
				st = i
				while i < len(arr) and nx == 1 + x and (ny + 1 == y):
					i += 1
					x = arr[i][0]
					y = arr[i][1]
					try:
						nx = arr[i + 1][0]
						ny = arr[i + 1][1]
					except:
						break
				end = i
				if arr[st] in bound and arr[end] in bound:
					ans = 1
					break
			else:
				i += 1
		if ans == 1:
			print('NO')
		else:
			print('YES')


inf = float('inf')
import sys
import pprint
import logging
from logging import getLogger
import array

def input():
	return sys.stdin.readline().rstrip('\r\n')

def maps():
	return [int(i) for i in input().split()]
logging.basicConfig(format='%(message)s', level=logging.WARNING)
logger = getLogger(__name__)
logger.setLevel(logging.INFO)

def debug(msg, *args):
	logger.info(f'{msg}={pprint.pformat(args)}')
from collections import defaultdict
from math import ceil
for _ in range(*maps()):
	(n,) = maps()
	d = defaultdict(int)
	r1 = c1 = r2 = c2 = None
	for i in range(n):
		(x, y) = maps()
		if x == 1:
			(r1, c1) = (x, y)
		if y == n:
			(r2, c2) = (x, y)
		d[x, y] += 1
	ok1 = ok2 = True
	cc = c1
	for i in range(cc):
		if not d[r1, c1]:
			ok1 = False
		r1 += 1
		c1 -= 1
	cc = n - r2 + 1
	for i in range(cc):
		if not d[r2, c2]:
			ok2 = False
		r2 += 1
		c2 -= 1
	print('NO') if ok1 or ok2 else print('YES')


from sys import stdin
input = stdin.readline

def down(i, j):
	count = 0
	while i <= n and j > 0 and pos.get((i, j), False):
		count += 1
		(i, j) = (i + 1, j - 1)
	return count

def up(i, j):
	count = 0
	while i > 0 and j <= n and pos.get((i, j), False):
		count += 1
		(i, j) = (i - 1, j + 1)
	return count

def answer():
	count1 = down(root1[0], root1[1])
	value1 = root1[1]
	count2 = up(root2[0], root2[1])
	value2 = n + 1 - root2[1]
	if count1 == value1 or count2 == value2:
		return 'NO'
	return 'YES'
for T in range(int(input())):
	n = int(input())
	pos = dict()
	for i in range(n):
		(x, y) = map(int, input().split())
		pos[x, y] = True
		if x == 1:
			root1 = [x, y]
		if x == n:
			root2 = [x, y]
	print(answer())


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(10 ** 7)

def dfs1(i, j):
	if i > n or j <= 0:
		return 0
	if pos.get((i + 1, j - 1), False):
		return dfs1(i + 1, j - 1) + 1
	return 1

def dfs2(i, j):
	if i <= 0 or j > n:
		return 0
	if pos.get((i - 1, j + 1), False):
		return dfs2(i - 1, j + 1) + 1
	return 1

def answer():
	count1 = dfs1(root1[0], root1[1])
	value1 = root1[1]
	count2 = dfs2(root2[0], root2[1])
	value2 = n + 1 - root2[1]
	if count1 == value1 or count2 == value2:
		return 'NO'
	return 'YES'
for T in range(int(input())):
	n = int(input())
	pos = dict()
	for i in range(n):
		(x, y) = map(int, input().split())
		pos[x, y] = True
		if x == 1:
			root1 = [x, y]
		if x == n:
			root2 = [x, y]
	print(answer())


t = int(input())
for z in range(t):
	n = int(input())
	d = dict()
	for i in range(n):
		(j, k) = map(int, input().split())
		if j + k not in d:
			d[j + k] = 1
		else:
			d[j + k] += 1
	n += 1
	flag = 0
	for (i, j) in d.items():
		if j == i - 1:
			print('NO')
			flag = 1
			break
		elif i > n and j == n + n - i - 1:
			print('NO')
			flag = 1
			break
	if flag == 0:
		print('YES')


from collections import *
from sys import *
input = stdin.readline
for u in range(int(input())):
	n = int(input())
	f = 0
	d = defaultdict(int)
	for i in range(n):
		(x, y) = map(int, input().split())
		d[x + y] += 1
	for i in d:
		if i != 2 and i != n + n:
			if d[i] == i - 1 or d[i] + i == 1 + 2 * n:
				f = 1
				break
	if f == 0:
		print('YES')
	else:
		print('NO')


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter
from collections import defaultdict as dd
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
stdmap = lambda : map(int, stdstr().split())
stdarr = lambda : list(map(int, stdstr().split()))
mod = 1000000007
for _ in range(stdint()):
	n = stdint()
	c = Counter()
	top = [-1, -1]
	end = [-1, -1]
	for i in range(n):
		(y, x) = stdmap()
		c[y, x] += 1
		if y == 1:
			top = [y, x]
		elif x == n:
			end = [y, x]
	blocked = True
	while top[0] <= n and top[1] > 0:
		if c[tuple(top)] > 0:
			top[0] += 1
			top[1] -= 1
		else:
			blocked = False
			break
	if not blocked and end[0] != -1 and (end[1] != -1):
		blocked1 = True
		while end[0] <= n and end[1] > 0:
			if c[tuple(end)] > 0:
				end[0] += 1
				end[1] -= 1
			else:
				blocked1 = False
				break
		blocked |= blocked1
	if blocked:
		print('NO')
	else:
		print('YES')


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	d = defaultdict(int)
	for _ in range(n):
		(x, y) = map(int, input().split())
		d[x + y] = d[x + y] + 1
	ans = True
	for i in range(3, 2 * n):
		if i <= n + 1:
			if d[i] == i - 1:
				ans = False
				break
		elif d[i] == n - i % n + 1:
			ans = False
			break
	if ans:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = []
	flag = 0
	ref = list(map(int, '0' * (2 * n + 1)))
	for i in range(n):
		l.append(sum(map(int, input().split())))
	for i in range(n):
		ref[l[i]] += 1
	for i in range(2, n + 2):
		if ref[i] == i - 1:
			flag = 1
			break
	for i in range(n + 2, 2 * n):
		if ref[i] == n - i % n + 1:
			flag = 1
			break
	print('NO' if flag else 'YES')


def max_diag_len(coord_sum, n):
	if coord_sum <= n + 1:
		return coord_sum - 1
	else:
		return 2 * n - coord_sum + 1

def main():
	t = int(input())
	for case_idx in range(t):
		n = int(input())
		coord_sums = [0] * (2 * n)
		can_cross = True
		for coord_idx in range(n):
			(i, j) = [int(x) for x in input().split()]
			coord_sums[i + j] += 1
			if coord_sums[i + j] >= max_diag_len(i + j, n):
				can_cross = False
		if can_cross:
			print('YES')
		else:
			print('NO')
main()


inf = float('inf')
import sys
import pprint
import logging
from logging import getLogger
import array

def input():
	return sys.stdin.readline().rstrip('\r\n')

def maps():
	return [int(i) for i in input().split()]
logging.basicConfig(format='%(message)s', level=logging.WARNING)
logger = getLogger(__name__)
logger.setLevel(logging.INFO)

def debug(msg, *args):
	logger.info(f'{msg}={pprint.pformat(args)}')
from collections import defaultdict
from math import ceil
for _ in range(*maps()):
	(n,) = maps()
	(arr, cnt1, cnt2) = ([], 0, 0)
	diags = 0
	d = defaultdict(int)
	(r1, c1) = (None, None)
	(r2, c2) = (None, None)
	for i in range(n):
		(x, y) = maps()
		if x == 1 and y == 2 or (x == 2 and y == 1):
			cnt1 += 1
		if x == n and y == n - 1 or (x == n - 1 and y == n):
			cnt2 += 1
		if x == 1:
			(r1, c1) = (x, y)
		if y == n:
			(r2, c2) = (x, y)
		arr.append([x, y])
		d[x, y] += 1
	if cnt1 == 2 or cnt2 == 2:
		print('NO')
		continue
	ok1 = True
	ok2 = True
	(C1, C2) = (0, 0)
	cc = c1
	for i in range(cc):
		if d[r1, c1]:
			C1 += 1
		else:
			ok1 = False
		r1 += 1
		c1 -= 1
	cc = n - r2 + 1
	for i in range(cc):
		if d[r2, c2]:
			C2 += 1
		else:
			ok2 = False
		r2 += 1
		c2 -= 1
	if ok1 or ok2:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	row = [0] * (n + 1)
	for i in range(n):
		(x, y) = list(map(int, input().split()))
		row[x] = y
	f = 0
	strt = row[n]
	for i in range(n - 1, 0, -1):
		if row[i] == strt + 1:
			strt += 1
			if strt == n:
				f = 1
				break
		else:
			break
	strt = row[1]
	for i in range(2, n + 1):
		if strt - 1 == row[i]:
			strt -= 1
			if strt == 1:
				f = 1
				break
		else:
			break
	if f:
		print('NO')
		continue
	print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append(tuple(map(int, input().split())))
	arr.sort()
	flag = 1
	ans = 'YES'
	for i in range(1, n):
		if arr[i][0] - arr[i - 1][0] == 0:
			pass
		elif (arr[i][1] - arr[i - 1][1]) / (arr[i][0] - arr[i - 1][0]) not in [1.0, -1.0]:
			flag = 0
		if flag == 1:
			if arr[i][1] == 1:
				ans = 'NO'
		if flag == 1 and i == n - 1:
			ans = 'NO'
	arr = arr[::-1]
	flag = 1
	for i in range(1, n):
		if arr[i][0] - arr[i - 1][0] == 0:
			pass
		elif (arr[i][1] - arr[i - 1][1]) / (arr[i][0] - arr[i - 1][0]) not in [1.0, -1.0]:
			flag = 0
		if flag == 1:
			if arr[i][1] == n:
				ans = 'NO'
		if flag == 1 and i == n - 1:
			ans = 'NO'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	temp = {}
	for i in range(n):
		(x, y) = map(int, input().split())
		if int(x + y) in temp:
			temp[x + y] += 1
		else:
			temp[x + y] = 1
	flag = 0
	if n > 2:
		for i in range(3, 2 * n):
			if i in temp and temp[i] == min(i - 1, 2 * n - i + 1):
				print('NO')
				flag = 1
				break
		if flag == 0:
			print('YES')
	elif temp[3] == 2:
		print('NO')
	else:
		print('YES')


from collections import defaultdict
for t in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	d = defaultdict(int)
	for a in l:
		k = a[0] + a[1]
		d[k] += 1
	c = 2
	for k in range(3, n * 2):
		if d[k] == c:
			print('NO')
			break
		if k > n:
			c -= 1
		else:
			c += 1
	else:
		print('YES')


t = int(input())

def f(tup):
	return tup[0]
for _ in range(t):
	n = int(input())
	blocks = []
	for i in range(n):
		(a, b) = map(int, input().split())
		blocks.append((a, b))
	blocks.sort(key=f)
	start = True
	no = False
	for i in range(1, n):
		if start:
			if blocks[i][1] + 1 == blocks[i - 1][1]:
				if blocks[i][0] == n or blocks[i][1] == 1:
					no = True
					break
			else:
				start = False
		if blocks[i][1] == n:
			start = True
	if no:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		(x, y) = map(int, input().split())
		a.append([x - 1, y - 1])
	a.sort()
	z = 1
	r = 0
	k = a[0][1]
	for i in range(n):
		if a[i][1] == k:
			pass
		else:
			z = 0
		k -= 1
		if k < 0:
			break
	z1 = 1
	k = a[n - 1][1]
	r1 = 0
	for i in range(n - 1, -1, -1):
		if a[i][1] == k:
			pass
		else:
			z1 = 0
		k += 1
		if k >= n:
			break
	if z == 0 and z1 == 0:
		print('YES')
	else:
		print('NO')


import sys
for t in range(int(input())):
	n = int(input())
	d = set()
	for i in range(n):
		(a, b) = map(int, input().split())
		d.add((a, b))
	t = False
	for j in range(2, n + 1):
		if (1, j) in d:
			flag = 1
			i = 1
			k = j
			while flag:
				if k == 0:
					t = True
					break
				elif (i, k) not in d:
					break
				else:
					i += 1
					k -= 1
			break
	if t:
		print('NO')
	else:
		for i in range(1, n):
			if (i, n) in d:
				j = i
				k = n
				while 1:
					if j > n:
						t = True
						break
					elif (j, k) not in d:
						break
					else:
						j += 1
						k -= 1
				break
		if t:
			print('NO')
		else:
			print('YES')


def func3(n):
	fm = [0 for i in range(2 * n)]
	for i in range(n):
		(x, y) = map(int, input().split())
		r = x + y
		fm[r] += 1
	l = 3
	r = 2 * n - 1
	c = 2
	while l <= r:
		if fm[l] == c or fm[r] == c:
			print('NO')
			return
		else:
			l += 1
			r -= 1
			c += 1
	print('YES')
	return
t = int(input())
for i in range(t):
	n = int(input())
	func3(n)


def main():
	t = int(input())
	while t > 0:
		n = int(input())
		fmap = [0 for i in range(2 * n)]
		for i in range(n):
			c = input().split()
			row = int(c[0])
			col = int(c[1])
			fmap[row + col] += 1
		left = 3
		right = 2 * n - 1
		val = 2
		ans = False
		while left <= right:
			if fmap[left] == val or fmap[right] == val:
				ans = True
				break
			else:
				left += 1
				right -= 1
				val += 1
		if ans:
			print('NO')
		else:
			print('YES')
		t -= 1
main()


import io, os, heapq, sys

def main():
	T = int(input())
	for _ in range(T):
		ans = 'YES'
		N = int(input())
		diags = {r: r for r in range(1, N + 1)}
		for c in range(2, N + 1):
			diags[N + c - 1] = N - c + 1
		for __ in range(N):
			(x, y) = [int(x) for x in input().split()]
			b = y + x - 1
			diags[b] -= 1
			if diags[b] <= 0:
				ans = 'NO'
		print(ans)
main()


from functools import lru_cache
import sys
import math
from collections import Counter, deque
mod = 10 ** 9 + 7
inf = float('inf')

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

def solve(n, blocks):

	def inBounds(i, j):
		return 1 <= i <= n and 1 <= j <= n
	Q = deque()
	visisted = set()
	for j in range(1, n + 1):
		if (1, j) in blocks:
			Q.append((1, j))
		if (j, n) in blocks:
			Q.append((j, n))
	for (i, j) in Q:
		to = (i, j)
		while to in blocks:
			to = (to[0] + 1, to[1] - 1)
			if not inBounds(*to):
				return 0
	return 1
TESTING = False
if TESTING:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	blocks = set()
	for _ in range(n):
		(a, b) = arrInt()
		blocks.add((a, b))
	ans = solve(n, blocks)
	res = ['NO', 'YES']
	print(res[ans])


import sys
sys.setrecursionlimit(1000000)
from functools import lru_cache
input = lambda : sys.stdin.readline().strip()

def dfs(x, y):
	if x == 1 or y == n:
		return True
	for (dx, dy) in ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, 1), (1, -1), (-1, -1)):
		if 1 <= x + dx <= n and 1 <= y + dy <= n and ((x + dx, y + dy) in blocks) and ((x + dx, y + dy) not in vis):
			vis.add((x + dx, y + dy))
			if dfs(x + dx, y + dy):
				return True
	return False
t = int(input())
while t:
	t -= 1
	n = int(input())
	blocks = set()
	vis = set()
	for i in range(n):
		(x, y) = map(int, input().split())
		blocks.add((x, y))
	ok = True
	for i in range(2, n + 1):
		if (i, 1) in blocks and (i, 1) not in vis and dfs(i, 1):
			vis.add((i, 1))
			ok = False
			break
		if (n, n - i + 1) in blocks and (n, n - i + 1) not in vis and dfs(n, n - i + 1):
			ok = False
			break
	if ok:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	N = int(input())
	ans = True
	G = [0] * (2 * N - 3)
	for i in range(N):
		(X, Y) = map(int, input().split())
		if ans:
			j = X + Y - 3
			G[j] += 1
			if G[j] == N - abs(X + Y - N - 1):
				ans = False
	print('YES' if ans else 'NO')


from collections import Counter
import sys
from collections import defaultdict as dd
from math import *

def vinp():
	return map(int, input().split())

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

def sinp():
	return input()

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

def mod(f):
	return f % 1000000007

def pr(*x):
	print(*x)

def finp():
	f = open('input.txt', 'r')
	f = f.read().split('\n')
	return f

def finp():
	f = open('input.txt', 'r')
	f = f.read().split('\n')
	return f

def fout():
	return open('output.txt', 'w')

def fpr(f, x):
	f.write(x + '\n')

def csort(c):
	sorted(c.items(), key=lambda pair: pair[1], reverse=True)

def indc(l, n):
	c = {}
	for i in range(n):
		c[l[i]] = c.get(l[i], []) + [i + 1]
	return c
cou = inp()
for _ in range(cou):
	n = inp()
	cnt = [0 for i in range(2 * n + 5)]
	for i in range(n):
		(a, b) = vinp()
		cnt[a + b] += 1
	flag = 0
	i = 2
	j = 1
	while i <= n and (not flag):
		if cnt[i] == j:
			flag = 1
		i += 1
		j += 1
	i = n + 1
	j = n
	while i <= 2 * n and (not flag):
		if cnt[i] == j:
			flag = 1
		i += 1
		j -= 1
	if flag:
		pr('NO')
	else:
		pr('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	blocks1 = []
	blockset = set()
	for _1 in range(n):
		(x, y) = map(int, input().split())
		blocks1.append((x, y))
		blockset.add((x, y))
	blocks1.sort()
	(x, y) = blocks1[0]
	while (x + 1, y - 1) in blockset:
		x += 1
		y -= 1
	if y == 1:
		print('NO')
	else:
		(x, y) = blocks1[-1]
		while (x - 1, y + 1) in blockset:
			x -= 1
			y += 1
		if y == n:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	n = int(input())
	b = []
	for i in range(n):
		b.append([int(i) for i in input().split()])
	b.sort(key=lambda x: x[1])
	d = 0
	i = 0
	while True:
		if b[i][0] == 1:
			d = 1
			break
		if b[i][0] == b[i + 1][0] + 1:
			i += 1
		else:
			break
	if d == 1:
		print('NO')
		continue
	b.sort(key=lambda x: -x[0])
	i = 0
	while True:
		if b[i][1] == n:
			d = 1
			break
		if b[i][1] == b[i + 1][1] - 1:
			i += 1
		else:
			break
	if d == 1:
		print('NO')
		continue
	print('YES')


from collections import Counter
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	d = Counter()
	bol = False
	for i in range(n):
		(x, y) = map(int, input().split())
		d[x + y] += 1
	for i in range(2, n + 1):
		if d[i + 1] == i or d[2 * n - i + 1] == i:
			bol = True
			break
	if bol:
		print('NO')
	else:
		print('YES')


def main():
	T = int(input())
	while T > 0:
		n = int(input())
		dic = {}
		dic_row = {}
		for i in range(n):
			(r, c) = map(int, input().split())
			dic[c] = r
			dic_row[r] = c
		start = dic[1]
		col = 1
		block = True
		while start > 0:
			if dic[col] != start:
				block = False
				break
			else:
				start -= 1
				col += 1
		if block is True:
			print('NO')
		else:
			block = True
			row = n
			start = dic_row[n]
			while start <= n:
				if dic_row[row] != start:
					block = False
					break
				else:
					start += 1
					row -= 1
			if block is True:
				print('NO')
			else:
				print('YES')
		T -= 1
main()


T = int(input())
for t in range(T):
	n = int(input())
	r = [0] * n
	c = [0] * n
	for i in range(n):
		(x, y) = [int(u) for u in input().split()]
		r[x - 1] = y - 1
		c[y - 1] = x - 1
	answer = True
	for i in range(1, n):
		if r[i] != r[i - 1] - 1:
			break
		if r[i] == 0:
			answer = False
			break
	for i in range(n - 2, -1, -1):
		if r[i] != r[i + 1] + 1:
			break
		if r[i] == n - 1:
			answer = False
			break
	if answer == True:
		print('YES')
	else:
		print('NO')


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = int(input())
	l1 = []
	l2 = [0 for i in range(2 * n + 1)]
	no = 0
	for i in range(n):
		(a, b) = list(map(int, input().split()))
		l1.append((a, b))
		l2[a + b] += 1
		if a + b <= n + 1 and l2[a + b] == a + b - 1:
			no = 1
		elif a + b > n + 1 and l2[a + b] == 2 * n - (a + b) + 1:
			no = 1
	if no == 1:
		print('NO')
	else:
		print('YES')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	rocks = {tuple(map(int, input().split())) for _ in range(n)}
	extrems = [rock for rock in rocks if rock[0] == 1 or rock[1] == n]
	puc = True
	for ex in extrems:
		if ex in rocks:
			rocks.remove(ex)
			nous = [ex]
			while nous:
				(x, y) = nous.pop()
				for i in range(-1, 2):
					for j in range(-1, 2):
						if not (i == 0 and j == 0):
							(nou_x, nou_y) = (x + i, y + j)
							if 1 <= nou_x <= n and 1 <= nou_y <= n:
								if (nou_x, nou_y) in rocks:
									if nou_x == n or nou_y == 1:
										puc = False
										break
									nous.append((nou_x, nou_y))
									rocks.remove((nou_x, nou_y))
				if not puc:
					break
		if not puc:
			break
	print('YES' if puc else 'NO')


q = int(input())
for _ in range(q):
	n = int(input())
	dic = {}
	ans = 'YES'
	for i in range(n):
		(x, y) = map(int, input().split())
		a = x + y
		dic[a] = dic.get(a, 0) + 1
	for (k, v) in dic.items():
		if k - v == 1 or k + v == 1 + 2 * n:
			ans = 'NO'
			break
	print(ans)


from collections import defaultdict
import sys
readline = sys.stdin.readline
T = int(readline())
for t in range(T):
	N = int(readline())
	dct = defaultdict(int)
	for i in range(N):
		(X, Y) = map(int, readline().split())
		dct[X + Y] += 1
	ans = 'YES'
	for (x, c) in dct.items():
		if c == min(x - 1, 2 * N + 1 - x):
			ans = 'NO'
	print(ans)