Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese] and [Bengali] as well.

Ada has two matrices $A$ and $B$, each with $N$ rows (numbered $1$ through $N$) and $N$ columns (numbered $1$ through $N$).

Ada may perform the following operation any number of times (including zero): choose an integer $i$ ($1 ≤ i ≤ N$), then swap row $i$ and column $i$ in matrix $A$. (Formally, for each valid $j$, she swaps $A_{i, j}$ with $A_{j, i}$.)

Is it possible to transform matrix $A$ into matrix $B$?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
$N$ lines follow. For each $i$ ($1 ≤ i ≤ N$), the $i$-th of these lines contains $N$ space-separated integers $A_{i, 1}, A_{i, 2}, \ldots, A_{i, N}$.
$N$ more lines follow. For each $i$ ($1 ≤ i ≤ N$), the $i$-th of these lines contains $N$ space-separated integers $B_{i, 1}, B_{i, 2}, \ldots, B_{i, N}$.

------  Output ------
For each test case, print a single line containing the string "Yes" if it is possible to transform $A$ into $B$ or "No" if it is impossible (without quotes).

------  Constraints  ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 2^{10}$
$1 ≤ A_{i, j}, B_{i, j} ≤ 10^{9}$ for each valid $i, j$
the sum of $N^{2}$ over all test cases does not exceed $3 \cdot 10^{6}$

----- Sample Input 1 ------ 
1

3

1 2 3

4 5 6

7 8 9

1 2 7

4 5 8

3 6 9
----- Sample Output 1 ------ 
Yes
----- explanation 1 ------ 
Example case 1: We can swap the second row with the second column and in the resulting matrix, swap the first row with the first column.

Difficulty: VERY_HARD
Tags: Strong connectivity

Graph algorithms

Data structures

Graph traversal
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	(n, A, B) = (int(input()), [], [])
	for _ in range(n):
		A.append(input().split())
	for _ in range(n):
		B.append(input().split())
	for i in range(n):
		for j in range(n):
			if A[i][j] != B[i][j] and A[i][j] == B[j][i]:
				for k in range(n):
					(A[k][j], A[j][k]) = (A[j][k], A[k][j])
	if A == B:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	a = []
	b = []
	Flag = False
	for i in range(n):
		a1 = list(map(int, input().split()))
		a.append(a1)
	for i in range(n):
		b1 = list(map(int, input().split()))
		b.append(b1)
	for i in range(n):
		for j in range(n):
			if a[i][j] != b[i][j]:
				for k in range(n):
					(a[j][k], a[k][j]) = (a[k][j], a[j][k])
	for i in range(n):
		for j in range(n):
			if a[i][j] != b[i][j]:
				Flag = True
				break
		if Flag:
			break
	if Flag:
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	N = int(input())
	array_A = []
	for x in range(N):
		a = [int(x) for x in input().split()]
		array_A.append(a)
	array_B = []
	for y in range(N):
		b = [int(x) for x in input().split()]
		array_B.append(b)
	for i in range(N):
		for j in range(N):
			if array_A[i][j] != array_B[i][j]:
				for k in range(N):
					temp = array_A[k][j]
					array_A[k][j] = array_A[j][k]
					array_A[j][k] = temp
	if array_A == array_B:
		print('Yes')
	else:
		print('No')


for p in range(int(input())):
	n = int(input())
	A = []
	B = []
	flag = 1
	for row in range(n):
		A.append(list(map(int, input().split())))
	for row in range(n):
		B.append(list(map(int, input().split())))
	for i in range(n):
		for j in range(n):
			if A[i][j] != B[i][j]:
				if A[j][i] == B[i][j] and i != j:
					for k in range(n):
						(A[j][k], A[k][j]) = (A[k][j], A[j][k])
				else:
					flag = 0
					break
		if not flag:
			break
	if flag and A == B:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	(n, a, b) = (int(input()), [], [])
	for i in range(n):
		a.append(input().split())
	for i in range(n):
		b.append(input().split())
	flag = True
	for i in range(n):
		if a[i][i] != b[i][i]:
			flag = False
			break
	if not flag:
		print('No')
		continue
	flag = False
	for i in range(n):
		for j in range(n):
			if a[i][j] == b[i][j]:
				continue
			if a[i][j] != b[i][j] and a[j][i] == b[i][j]:
				for k in range(n):
					(a[j][k], a[k][j]) = (a[k][j], a[j][k])
			else:
				flag = True
				break
		if flag:
			break
	if flag:
		print('No')
		continue
	if a == b:
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	b = []
	for i in range(n):
		line = [int(i) for i in input().split()]
		a.append(line)
	for i in range(n):
		line = [int(i) for i in input().split()]
		b.append(line)
	for i in range(n):
		for j in range(n):
			if a[i][j] != b[i][j]:
				for k in range(n):
					(a[k][j], a[j][k]) = (a[j][k], a[k][j])
	if a == b:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	N = int(input())
	A = []
	B = []
	flag = True
	for i in range(N):
		A.append([int(i) for i in input().split(' ')])
	for i in range(N):
		B.append([int(x) for x in input().split(' ')])
	for i in range(N):
		for j in range(N):
			if A[i][j] != B[i][j]:
				for k in range(N):
					(A[k][j], A[j][k]) = (A[j][k], A[k][j])
	for i in range(N):
		for j in range(N):
			if A[i][j] != B[i][j]:
				flag = False
				break
	if flag:
		print('Yes')
	else:
		print('No')


t = int(input())
while t:
	t -= 1
	n = int(input())
	arr1 = []
	arr2 = []
	f = 0
	for i in range(n):
		arr1.append(list(map(int, input().strip().split())))
	for i in range(n):
		arr2.append(list(map(int, input().strip().split())))
	for i in range(n):
		for j in range(n):
			if arr1[i][j] != arr2[i][j]:
				for k in range(n):
					tmp = arr1[j][k]
					arr1[j][k] = arr1[k][j]
					arr1[k][j] = tmp
	for i in range(n):
		for j in range(n):
			if arr1[i][j] != arr2[i][j]:
				f = 1
				break
		if f == 1:
			break
	if f == 1:
		print('No')
	else:
		print('Yes')


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	l1 = []
	l2 = []
	for i in range(n):
		l1.append([int(x) for x in input().split()])
	for i in range(n):
		l2.append([int(x) for x in input().split()])
	theer = True
	for i in range(n):
		for j in range(n):
			if l1[i][j] == l2[i][j]:
				if not l1[j][i] == l2[j][i]:
					theer = False
					break
			if l1[i][j] == l2[j][i]:
				if not l1[j][i] == l2[i][j]:
					theer = False
					break
	if not theer:
		print('No')
		continue

	def transpose(l1, j):
		jthrow = l1[j]
		jthcol = []
		for i in range(len(l1)):
			jthcol.append(l1[i][j])
			l1[i][j] = jthrow[i]
		l1[j] = jthcol
	for i in range(n):
		for j in range(n):
			if l1[i][j] == l2[i][j]:
				continue
			else:
				transpose(l1, j)
	for i in range(n):
		for j in range(n):
			if l1[i][j] != l2[i][j]:
				theer = False
				break
	if not theer:
		print('No')
		continue
	else:
		print('Yes')
		continue


def main():
	for _ in range(int(input())):
		n = int(input())
		m1 = []
		m2 = []
		for i in range(n):
			l = list(map(int, input().split()))
			m1.append(l)
		for i in range(n):
			l = list(map(int, input().split()))
			m2.append(l)
		for i in range(n):
			for j in range(n):
				if m1[i][j] != m2[i][j] and m1[j][i] == m2[i][j]:
					temp = []
					for k in range(n):
						temp.append(m1[k][j])
					x = m1[j]
					m1[j] = temp
					for k in range(n):
						m1[k][j] = x[k]
		if m1 == m2:
			print('Yes')
		else:
			print('No')
main()