You are given a table consisting of n rows and m columns.

Numbers in each row form a permutation of integers from 1 to m.

You are allowed to pick two elements in one row and swap them, but no more than once for each row. Also, no more than once you are allowed to pick two columns and swap them. Thus, you are allowed to perform from 0 to n + 1 actions in total. Operations can be performed in any order.

You have to check whether it's possible to obtain the identity permutation 1, 2, ..., m in each row. In other words, check if one can perform some of the operation following the given rules and make each row sorted in increasing order.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 20) — the number of rows and the number of columns in the given table. 

Each of next n lines contains m integers — elements of the table. It's guaranteed that numbers in each line form a permutation of integers from 1 to m.


-----Output-----

If there is a way to obtain the identity permutation in each row by following the given rules, print "YES" (without quotes) in the only line of the output. Otherwise, print "NO" (without quotes).


-----Examples-----
Input
2 4
1 3 2 4
1 3 4 2

Output
YES

Input
4 4
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

Output
NO

Input
3 6
2 1 3 4 5 6
1 2 4 3 5 6
1 2 3 4 6 5

Output
YES



-----Note-----

In the first sample, one can act in the following way:   Swap second and third columns. Now the table is 1 2 3 4 1 4 3 2  In the second row, swap the second and the fourth elements. Now the table is 1 2 3 4 1 2 3 4

Difficulty: MEDIUM
Tags: Mathematics

Complete search

Implementation

Greedy algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
def get_perms(perm):
	perms = {tuple(perm)}
	for i in range(len(perm)):
		for j in range(i + 1, len(perm)):
			perm_copy = list(perm)
			(perm_copy[i], perm_copy[j]) = (perm_copy[j], perm_copy[i])
			perms.add(tuple(perm_copy))
	return perms
(n, m) = list(map(int, input().split(' ')))
good_perms = get_perms([i for i in range(1, m + 1)])
for i in range(n):
	perm = list(map(int, input().split(' ')))
	good_perms &= get_perms(perm)
if good_perms:
	print('YES')
else:
	print('NO')


(n, m) = [int(x) for x in input().split()]
L = [[int(x) for x in input().split()] for i in range(n)]

def solve(L):
	D = {i: set() for i in range(n)}
	for i in range(n):
		for j in range(m):
			if L[i][j] != j + 1:
				D[i].add((min(j + 1, L[i][j]), max(j + 1, L[i][j])))
				if len(D[i]) > 3 or (len(D[i]) == 3 and L[i][L[i][j] - 1] == j + 1):
					return False
	if all((len(D[i]) < 2 for i in range(n))):
		return True
	for x in range(m):
		for y in range(x, m):
			for i in range(n):
				if not ((x + 1, y + 1) in D[i] or len(D[i]) == 0):
					break
			else:
				return True
	return False
print('YES') if solve(L) else print('NO')


def cntmisp(a):
	return sum([int(a[i] != i + 1) for i in range(len(a))])
(n, m) = [int(x) for x in input().split(' ')]
a = []
for i in range(n):
	a.append([int(x) for x in input().split(' ')])
cnts = [cntmisp(x) for x in a]
fl = 0
if max(cnts) <= 2:
	print('YES')
else:
	for p1 in range(m - 1):
		for p2 in range(p1 + 1, m):
			A = []
			for i in range(n):
				subA = []
				for p in range(m):
					if p == p1:
						subA.append(a[i][p2])
					elif p == p2:
						subA.append(a[i][p1])
					else:
						subA.append(a[i][p])
				A.append(list(subA))
			newcnts = [cntmisp(x) for x in A]
			if max(newcnts) <= 2:
				fl = 1
	print('YES' if fl else 'NO')


from copy import deepcopy
(n, m) = list(map(int, input().split()))
arr = []
for i in range(n):
	arr.append(list(map(int, input().split())))

def solve(arr):
	for row in arr:
		count = 0
		for (i, num) in enumerate(row):
			if i + 1 != num:
				count += 1
				if count > 2:
					return False
	return True

def permute(arr, i, j):
	arr_ = deepcopy(arr)
	for k in range(n):
		(arr_[k][i], arr_[k][j]) = (arr_[k][j], arr_[k][i])
	return arr_

def main():
	if solve(arr):
		print('YES')
		return
	for row in arr:
		wrong_cols = []
		for (i, num) in enumerate(row):
			if i + 1 != num:
				wrong_cols.append(i)
		if wrong_cols:
			if len(wrong_cols) > 4:
				print('NO')
				return
			for col in wrong_cols:
				if solve(permute(arr, col, row[col] - 1)):
					print('YES')
					return
			print('NO')
			return
	print('NO')
	return
main()


def check(table):
	n = len(table)
	m = len(table[0])
	bits = [[table[i][j] == j + 1 for j in range(m)] for i in range(n)]
	for row in bits:
		if row.count(False) > 2:
			return False
	return True
(n, m) = list(map(int, input().split()))
table = [list(map(int, input().split())) for i in range(n)]
for i in range(m - 1):
	for j in range(i, m):
		_table = [table[i][:] for i in range(n)]
		for k in range(n):
			(_table[k][i], _table[k][j]) = (_table[k][j], _table[k][i])
		if check(_table):
			print('YES')
			return
if check(table):
	print('YES')
	return
print('NO')


import copy

def check(table, n, m):
	table1 = copy.deepcopy(table)
	for i in range(n):
		indices = []
		for j in range(m):
			if table1[i][j] != j + 1:
				indices.append(j)
		if len(indices) > 2:
			return False
		if indices:
			(table1[i][indices[0]], table1[i][indices[1]]) = (table1[i][indices[1]], table1[i][indices[0]])
		for j in range(m):
			if table1[i][j] != j + 1:
				return False
	return True

def swap(table, i, j, n, m):
	for k in range(n):
		(table[k][i], table[k][j]) = (table[k][j], table[k][i])

def solve(table, n, m):
	for i in range(m):
		for j in range(i, m):
			swap(table, i, j, n, m)
			if check(table, n, m):
				print('YES')
				return
			swap(table, i, j, n, m)
	print('NO')

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


def check(matrix, getindex=False, isfirst=False):
	indices = set()
	canbe = True
	for row in matrix:
		count = 0
		for (i, value) in enumerate(row):
			if value != i + 1:
				indices.update([i])
				count += 1
		if count > 2:
			canbe = False
		if count > 4 and isfirst:
			print('NO')
			exit()
	if getindex:
		return list(indices)
	return canbe
(n, m) = map(int, input().split())
matrix = []
for i in range(n):
	row = [int(x) for x in input().split()]
	matrix.append(row)
indices = check(matrix, True, True)
canbesort = check(matrix)
for i in indices:
	if canbesort:
		break
	for j in indices[1:]:
		for k in range(n):
			(matrix[k][i], matrix[k][j]) = (matrix[k][j], matrix[k][i])
			canbesort = check(matrix)
		if canbesort:
			break
		for k in range(n):
			(matrix[k][i], matrix[k][j]) = (matrix[k][j], matrix[k][i])
print(canbesort and 'YES' or 'NO')


def main():
	from itertools import combinations
	(n, m) = map(int, input().split())
	l = []
	for _ in range(n):
		row = list(map(int, input().split()))
		l.append(sorted(range(m), key=row.__getitem__))
	for (i, j) in [(0, 0), *combinations(range(m), 2)]:

		def inner(row):
			line = row[:]
			(line[i], line[j]) = (line[j], line[i])
			flag = False
			for u in range(m):
				while u < line[u]:
					if flag:
						return False
					(flag, v) = (True, line[u])
					(line[u], line[v]) = (line[v], v)
			return True
		if all(map(inner, l)):
			print('YES')
			return
	print('NO')
main()


(n, m) = map(int, input().split(' '))
a = []
for i in range(n):
	a.append(list(map(int, input().split(' '))))
p = []
possible = True
col_swap = False
for r in a:
	x = []
	j = 0
	swaps = []
	while j < len(r) and len(swaps) < 3:
		if r[j] != j + 1:
			tmp = r[j]
			r[j] = r[tmp - 1]
			r[tmp - 1] = tmp
			swaps.append((j, tmp - 1))
		else:
			j += 1
	if len(swaps) > 2:
		possible = False
		break
	if len(swaps) == 2:
		col_swap = True
	if len(swaps) > 0:
		x = swaps
		if len(swaps) == 2 and swaps[0][0] == swaps[1][0]:
			x.append((min(swaps[0][1], swaps[1][1]), max(swaps[0][1], swaps[1][1])))
		p.append(x)
if possible and col_swap and p:
	c = set(p[0])
	for x in p:
		c = c.intersection(x)
	possible = bool(c)
if possible:
	print('YES')
else:
	print('NO')


def judge():
	(n, m) = list(map(int, input().split()))
	num = [list(map(int, input().split())) for x in range(n)]
	for i in range(m):
		for j in range(m):
			tmp = num[:]
			for k in range(n):
				(tmp[k][i], tmp[k][j]) = (tmp[k][j], tmp[k][i])
			cur = True
			for k in range(n):
				cnt = len([l for l in range(m) if tmp[k][l] != l + 1])
				if cnt > 2:
					cur = False
			for k in range(n):
				(tmp[k][i], tmp[k][j]) = (tmp[k][j], tmp[k][i])
			if cur:
				return True
	return False
if judge():
	print('YES')
else:
	print('NO')


from sys import stdin
from sys import stdout
from sys import exit
nm = [int(x) for x in stdin.readline()[:-1].split(' ')]
n = nm[0]
m = nm[1]
matrice = [[] for z in range(n)]
for i in range(n):
	matrice[i] = [int(x) for x in stdin.readline()[:-1].split(' ')]
cancomplete = False
a = [[0 for i in range(n)] for j in range(m)]
for colonna in range(m):
	for riga in range(n):
		a[colonna][riga] = matrice[riga][colonna]
for i in range(m):
	for j in range(i, m):
		o = a[:]
		tieni = o[i][:]
		o[i] = o[j][:]
		o[j] = tieni[:]
		trycomplete = True
		for riga in range(n):
			conto = 0
			for colonna in range(m):
				if o[colonna][riga] != colonna + 1:
					conto += 1
			if conto > 2:
				trycomplete = False
		cancomplete = cancomplete or trycomplete
if cancomplete:
	stdout.write('YES')
else:
	stdout.write('NO')


(n, m) = map(int, input().strip().split(' '))
g = [list(map(int, input().strip().split(' '))) for i in range(n)]

def check(a, b):
	for row in g:
		(row[a], row[b]) = (row[b], row[a])
		mis_placed = 0
		for i in range(1, m + 1):
			if row[i - 1] != i:
				mis_placed += 1
		(row[a], row[b]) = (row[b], row[a])
		if mis_placed > 2:
			return False
	return True
yes = check(0, 0)
for a in range(0, m - 1):
	for b in range(a + 1, m):
		if check(a, b):
			yes = True
print('YES' if yes else 'NO')


import sys, re, itertools
rai = lambda x: list(map(int, x.split()))

def pm(a):
	for l in a:
		print(l)
	print()
_use_stdin = True
if _use_stdin:
	inp = sys.stdin
else:
	inp = open('input.txt', 'r')
ls = inp.read().splitlines()
(n, m) = rai(ls[0])
a = [rai(l) for l in ls[1:]]
b = list(range(1, m + 1))
c = []

def f(x):
	t = 0
	for (i, x) in enumerate(a[x]):
		if x != b[i]:
			t += 1
	return t
flag = False
for i in range(m):
	for j in range(i, m):
		for k in range(n):
			(a[k][i], a[k][j]) = (a[k][j], a[k][i])
		flag2 = True
		for k in range(n):
			if f(k) > 2:
				flag2 = False
				break
		if not flag:
			flag = flag2
		for k in range(n):
			(a[k][i], a[k][j]) = (a[k][j], a[k][i])
print('YES' if flag else 'NO')


(n, m) = list(map(int, input().split()))

def f(a):
	nonlocal c, k
	c = []
	k = 0
	for i in range(m):
		if a[i] - 1 != i:
			k += 1
			c.append(i)
c = []
bb = []
cc = []
k = 0
flag1 = True
flag = True
for i in range(n):
	b = list(map(int, input().split()))
	f(b)
	if k > 2:
		flag1 = False
	if k > 2:
		if k > 4:
			print('NO')
			flag = False
			break
		elif cc == []:
			for j in range(len(c)):
				cc.append(c[j])
		elif k == 3:
			cc = []
			for j in range(len(c)):
				cc.append(c[j])
	bb.append(b)
if flag1:
	print('YES')
elif flag:
	for i in range(n):
		(bb[i][cc[0]], bb[i][cc[1]]) = (bb[i][cc[1]], bb[i][cc[0]])
		f(bb[i])
		if k > 2:
			flag = False
		(bb[i][cc[0]], bb[i][cc[1]]) = (bb[i][cc[1]], bb[i][cc[0]])
	if flag:
		print('YES')
	else:
		flag = True
		for i in range(n):
			(bb[i][cc[0]], bb[i][cc[2]]) = (bb[i][cc[2]], bb[i][cc[0]])
			f(bb[i])
			if k > 2:
				flag = False
			(bb[i][cc[0]], bb[i][cc[2]]) = (bb[i][cc[2]], bb[i][cc[0]])
		if flag:
			print('YES')
		else:
			flag = True
			for i in range(n):
				(bb[i][cc[1]], bb[i][cc[2]]) = (bb[i][cc[2]], bb[i][cc[1]])
				f(bb[i])
				if k > 2:
					flag = False
				(bb[i][cc[1]], bb[i][cc[2]]) = (bb[i][cc[2]], bb[i][cc[1]])
			if flag:
				print('YES')
			elif len(cc) == 3:
				print('NO')
			else:
				flag = True
				for i in range(n):
					(bb[i][cc[0]], bb[i][cc[3]]) = (bb[i][cc[3]], bb[i][cc[0]])
					f(bb[i])
					if k > 2:
						flag = False
					(bb[i][cc[0]], bb[i][cc[3]]) = (bb[i][cc[3]], bb[i][cc[0]])
				if flag:
					print('YES')
				else:
					flag = True
					for i in range(n):
						(bb[i][cc[1]], bb[i][cc[3]]) = (bb[i][cc[3]], bb[i][cc[1]])
						f(bb[i])
						if k > 2:
							flag = False
						(bb[i][cc[1]], bb[i][cc[3]]) = (bb[i][cc[3]], bb[i][cc[1]])
					if flag:
						print('YES')
					else:
						flag = True
						for i in range(n):
							(bb[i][cc[2]], bb[i][cc[3]]) = (bb[i][cc[3]], bb[i][cc[2]])
							f(bb[i])
							if k > 2:
								flag = False
							(bb[i][cc[2]], bb[i][cc[3]]) = (bb[i][cc[3]], bb[i][cc[2]])
						if flag:
							print('YES')
						else:
							print('NO')


import copy
(n, m) = map(int, input().split())
l = []
for i in range(n):
	l.append(list(map(int, input().split())))

def test_matrix(l):
	test = 1
	for i in range(n):
		rem = 0
		k = 1
		for j in range(m):
			if l[i][j] != j + 1 and rem == 0:
				rem = {j + 1, l[i][j]}
			elif l[i][j] != j + 1 and l[i][j] not in rem:
				k = 0
				break
		if k == 0:
			test = 0
			break
	if test == 0:
		return False
	else:
		return True
ola = 0
if test_matrix(l) == True:
	ola = 1
for i in range(m):
	for j in range(i + 1, m):
		b = copy.deepcopy(l)
		for p in range(n):
			(b[p][i], b[p][j]) = (b[p][j], b[p][i])
		if test_matrix(b) == True:
			ola = 1
			break
	if ola == 1:
		break
if ola == 1:
	print('YES')
else:
	print('NO')


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

def check(x, y):
	for i in range(n):
		k = 0
		for j in range(m):
			if j == x:
				if a[i][y] != j + 1:
					k += 1
			elif j == y:
				if a[i][x] != j + 1:
					k += 1
			elif a[i][j] != j + 1:
				k += 1
		if k > 2:
			return False
	return True
for e in range(m):
	for r in range(m):
		if check(e, r):
			print('YES')
			return
print('NO')


from collections import defaultdict

def getdiff(l):
	diff = []
	for i in range(m):
		if l[i] != i + 1:
			diff.append(l[i])
	return diff
(n, m) = list(map(int, input().split()))
t = [list(map(int, input().split())) for i in range(n)]
diffs = [defaultdict(bool) for i in range(n)]
for j in range(m):
	for j2 in range(j, m):
		for i in range(n):
			(t[i][j], t[i][j2]) = (t[i][j2], t[i][j])
			df = getdiff(t[i])
			(t[i][j], t[i][j2]) = (t[i][j2], t[i][j])
			if len(df) == 2:
				diffs[i][tuple(sorted(df))] = True
for j in range(m):
	for j2 in range(j, m):
		for i in range(n):
			if j != j2 and (not diffs[i][j + 1, j2 + 1]):
				break
			(t[i][j], t[i][j2]) = (t[i][j2], t[i][j])
			df = getdiff(t[i])
			(t[i][j], t[i][j2]) = (t[i][j2], t[i][j])
			if len(df) > 2:
				break
		else:
			print('YES')
			return
print('NO')


import sys
(n, m) = list(map(int, input().split()))
g = [list(map(int, input().split())) for _ in range(n)]
for c1 in range(m):
	for c2 in range(c1, m):
		ok = True
		for row in g:
			(row[c1], row[c2]) = (row[c2], row[c1])
			cnt = 0
			for i in range(m):
				if row[i] != i + 1:
					cnt += 1
				if cnt > 2:
					break
			(row[c1], row[c2]) = (row[c2], row[c1])
			if cnt > 2:
				ok = False
				break
		if ok:
			print('YES')
			return
print('NO')


from sys import stdin
(n, m) = (int(x) for x in stdin.readline().split())
table = []
for _ in range(n):
	table.append([int(x) for x in stdin.readline().split()])

def tr(l):
	return list(map(list, zip(*l)))

def need_one_or_zero_swap(l):
	swap = 2
	for (i, item) in enumerate(l):
		if item != i + 1:
			if swap:
				if l[item - 1] == i + 1:
					swap -= 1
				else:
					return False
			else:
				return False
	return True

def check_after_global_swap(t):
	for row in t:
		if not need_one_or_zero_swap(row):
			return False
	return True

def try_global_swap_first():
	if check_after_global_swap(table):
		return True
	transp = tr(table)
	for i in range(len(transp)):
		for j in range(i + 1, len(transp)):
			(transp[i], transp[j]) = (transp[j], transp[i])
			t2 = tr(transp)
			if check_after_global_swap(t2):
				return True
			(transp[i], transp[j]) = (transp[j], transp[i])
	return False
if try_global_swap_first():
	print('YES')
else:
	print('NO')


import sys

def swapC(c1, c2):
	for r in range(n):
		swap(r, c1, c2)

def swap(r, c1, c2):
	(nums[r][c1], nums[r][c2]) = (nums[r][c2], nums[r][c1])

def checkRow(r):
	bad = []
	for i in range(m):
		if nums[r][i] != i:
			bad.append(i)
	if len(bad) == 0:
		return True
	if len(bad) != 2:
		return False
	(x0, x1) = (nums[r][bad[0]], nums[r][bad[1]])
	return bad[0] == x1 and bad[1] == x0

def checkAll():
	for r in range(n):
		if not checkRow(r):
			return False
	return True
(n, m) = map(int, input().split())
nums = [list(map(lambda x: int(x) - 1, input().split())) for i in range(n)]
flag = False
for c1 in range(m):
	for c2 in range(c1, m):
		swapC(c1, c2)
		if checkAll():
			print('YES')
			flag = True
			break
		swapC(c1, c2)
	if flag:
		break
else:
	print('NO')


from sys import stdin, stdout
from copy import deepcopy

def rint():
	return map(int, stdin.readline().split())
(r, c) = rint()
mat = [[] for i in range(r)]
for i in range(r):
	mat[i] = list(rint())
orimat = deepcopy(mat)
notok = 0
for i in range(c):
	for j in range(i + 1, c):
		mat = deepcopy(orimat)
		for k in range(r):
			(mat[k][j], mat[k][i]) = (mat[k][i], mat[k][j])
			cnt = 0
			for l in range(c):
				if mat[k][l] != l + 1:
					cnt += 1
			if cnt > 2:
				break
		else:
			print('YES')
			exit()
mat = deepcopy(orimat)
for k in range(r):
	cnt = 0
	for l in range(c):
		if mat[k][l] != l + 1:
			cnt += 1
	if cnt > 2:
		print('NO')
		break
else:
	print('YES')


from copy import deepcopy
(n, m) = input().split(' ')
array = []
for i in range(int(n)):
	row = [int(i) for i in input().split(' ')]
	array.append(row)

def check(ar):
	return [i for i in range(len(ar)) if ar[i] != i + 1]

def sorting(mass):
	if all((len(check(i)) <= 2 for i in mass)):
		return 'YES'
	mass2 = deepcopy(mass)
	k = list()
	for i in mass:
		if check(i):
			k = check(i)
			break
	for i in k:
		for j in k:
			if i == j:
				continue
			for s in mass2:
				(s[i], s[j]) = (s[j], s[i])
			if all((len(check(k)) <= 2 for k in mass2)):
				return 'YES'
			mass2 = deepcopy(mass)
	return 'NO'
print(sorting(array))


I = lambda : map(int, input().split())
R = range
(n, m) = I()
t = [[] for _ in R(m)]
e = list(R(1, m + 1))
r = 'NO'
for _ in R(n):
	for (i, v) in zip(R(m), I()):
		t[i] += [v]
for i in R(m):
	for j in R(i, m):
		(t[i], t[j]) = (t[j], t[i])
		if all((3 > sum((t[i][j] != e[i] for i in R(m))) for j in R(n))):
			r = 'YES'
		(t[i], t[j]) = (t[j], t[i])
print(r)


def difference(ln, k, l):
	count = 0
	line2 = ln[:]
	(line2[k], line2[l]) = (ln[l], ln[k])
	for i in range(len(ln)):
		if line2[i] != i + 1:
			count += 1
	return count

def difference2(ln):
	count = 0
	for i in range(len(ln)):
		if ln[i] != i + 1:
			count += 1
	return count

def __starting_point():
	(n, m) = input().split(' ')
	n = int(n)
	m = int(m)
	matrix = []
	for i in range(n):
		line = [int(i) for i in input().split(' ')]
		matrix.append(line)
	res = False
	ans = True
	for line in matrix:
		if difference2(line) > 2:
			ans = False
	if ans:
		res = True
	for i in range(m):
		for j in range(m):
			if i == j:
				continue
			answer = True
			for line in matrix:
				if difference(line, i, j) > 2:
					answer = False
			if answer == True:
				res = True
	if res:
		print('YES')
	else:
		print('NO')
__starting_point()


import random

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)
(n, m) = map(int, input().split())
a = []
ans = 0
for i in range(n):
	a.append(list(map(int, input().split())))
for i in range(m):
	for j in range(i + 1, m):
		for k in range(n):
			t = a[k][i]
			a[k][i] = a[k][j]
			a[k][j] = t
		f = 0
		for r in range(n):
			che = 1
			cnt = 0
			for c in range(m):
				if a[r][c] != che:
					cnt += 1
				che += 1
			if cnt > 2:
				f = 1
				break
		if f == 0:
			ans = 1
			break
		for k in range(n):
			t = a[k][i]
			a[k][i] = a[k][j]
			a[k][j] = t
	if ans == 1:
		break
f = 0
for r in range(n):
	che = 1
	cnt = 0
	for c in range(m):
		if a[r][c] != che:
			cnt += 1
		che += 1
	if cnt > 2:
		f = 1
		break
if f == 0:
	ans = 1
if ans == 1:
	print('YES')
else:
	print('NO')


def no(k):
	s = []
	for j in range(len(k)):
		if k[j] != j + 1:
			s.append(j)
	return s

def summ(k, n, i):
	s = 0
	for j in range(n):
		s += k[j][i]
	return s

def numcol(k, n):
	d = 0
	s = no(k[0])
	for i in s:
		if summ(k, n, i) == n * k[0][i]:
			d += 1
	return d

def notin(k, m):
	s = 0
	for j in range(m):
		if k[j] != j + 1:
			s += 1
	return s

def somme(k, n, m):
	g = 0
	for i in range(n):
		g += notin(k[i], m)
	return g

def op(k, n, m):
	for i in range(n):
		if notin(k[i], m) > 2:
			return False
	return True

def tr(l, n, m, i, j):
	c = l.copy()
	for s in range(n):
		(c[s][i], c[s][j]) = (c[s][j], c[s][i])
		f = op(c, n, m)
	for s in range(n):
		(c[s][i], c[s][j]) = (c[s][j], c[s][i])
	return f

def main():
	(n, m) = map(int, input().split())
	k = []
	for i in range(n):
		k.append(list(map(int, input().split(' '))))
	g = somme(k, n, m)
	h = -1
	f = -1
	for i in range(n):
		if notin(k[i], m) > 4:
			return 'NO'
		elif notin(k[i], m) == 4:
			f = i
		elif notin(k[i], m) == 3:
			h = i
	if n < 3 and m < 3:
		return 'YES'
	elif h == -1 and f == -1:
		return 'YES'
	elif h != -1:
		p = no(k[h])
		if tr(k, n, m, p[0], p[1]) or tr(k, n, m, p[0], p[2]) or tr(k, n, m, p[1], p[2]):
			return 'YES'
		else:
			return 'NO'
	elif h == -1:
		p = no(k[f])
		if tr(k, n, m, p[0], p[1]) or tr(k, n, m, p[0], p[2]) or tr(k, n, m, p[0], p[3]) or tr(k, n, m, p[1], p[2]) or tr(k, n, m, p[1], p[3]) or tr(k, n, m, p[2], p[3]):
			return 'YES'
		else:
			return 'NO'
print(main())


from sys import stdin, stdout

def check():
	global numbers
	for z in range(n):
		cnt = 0
		chal = numbers[z][:]
		for j in range(m):
			if chal[j] != j + 1:
				cnt += 1
			for k in range(j + 1, m):
				if chal[k] == j + 1:
					(chal[k], chal[j]) = (chal[j], chal[k])
					break
		if cnt > 1:
			return 0
	else:
		return 1
(n, m) = map(int, stdin.readline().split())
numbers = []
for i in range(n):
	numbers.append(list(map(int, stdin.readline().split())))
challengers = []
for i in range(m):
	for j in range(i, m):
		challengers.append((i, j))
label = 0
for (a, b) in challengers:
	for j in range(n):
		(numbers[j][a], numbers[j][b]) = (numbers[j][b], numbers[j][a])
	label = max(check(), label)
	for j in range(n):
		(numbers[j][a], numbers[j][b]) = (numbers[j][b], numbers[j][a])
if not label:
	stdout.write('NO')
else:
	stdout.write('YES')


def chk(matrixx):
	for row in matrixx:
		count = 0
		for (i, val) in enumerate(row):
			if val != i + 1:
				count += 1
			if count > 2:
				return False
	return True
(n, m) = [int(x) for x in input().split()]
matrix = []
for i in range(n):
	row = [int(x) for x in input().split()]
	matrix.append(row)
possible = chk(matrix)
for p in range(m):
	if possible:
		break
	for q in range(p + 1, m):
		for row in range(n):
			(matrix[row][p], matrix[row][q]) = (matrix[row][q], matrix[row][p])
		possible = chk(matrix)
		if possible:
			break
		for row in range(n):
			(matrix[row][p], matrix[row][q]) = (matrix[row][q], matrix[row][p])
print(possible and 'YES' or 'NO')


(n, m) = list(map(int, input().split()))
inp = [input() for _ in range(n)]
mat = [[] for _ in range(m)]
for row in inp:
	r = row.split()
	for (idx, val) in enumerate(r):
		mat[idx].append(int(val))

def valid(row):
	count = 0
	for (idx, col) in enumerate(mat):
		if idx + 1 != col[row]:
			count += 1
			if count > 2:
				return False
	return count <= 2

def try_swap(col1, col2):
	temp = mat[col1]
	mat[col1] = mat[col2]
	mat[col2] = temp
	for row in range(n):
		if not valid(row):
			temp = mat[col2]
			mat[col2] = mat[col1]
			mat[col1] = temp
			return False
	temp = mat[col2]
	mat[col2] = mat[col1]
	mat[col1] = temp
	return True
for col in range(m):
	for col2 in range(col + 1, m):
		if try_swap(col, col2):
			print('YES')
			import sys
			return
if try_swap(0, 0):
	print('YES')
else:
	print('NO')


import itertools
import bisect
import math
from collections import *
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(10 ** 5)
ii = lambda : int(input())
lmii = lambda : list(map(int, input().split()))
slmii = lambda : sorted(map(int, input().split()))
li = lambda : list(input())
mii = lambda : map(int, input().split())
msi = lambda : map(str, input().split())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def ncr(n, r):
	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def npr(n, r):
	return math.factorial(n) // math.factorial(n - r)

def main():
	(n, m) = mii()
	lst = []
	f = 0
	for i in range(n):
		a = lmii()
		lst.append(a)
	for i in range(n):
		d = defaultdict(int)
		for j in range(m):
			if j + 1 != lst[i][j]:
				d[j + 1] = lst[i][j]
		if len(d) > 4:
			print('NO')
			exit(0)
	for i in range(n):
		d = defaultdict(int)
		for j in range(m):
			if j + 1 != lst[i][j]:
				d[j + 1] = lst[i][j]
		if len(d) > 2:
			f = 1
			break
		for j in d:
			if j != d[d[j]]:
				f = 1
				break
		if f == 1:
			break
	if f == 0:
		print('YES')
	else:
		for i in range(m):
			for j in range(i + 1, m):
				col1 = i
				col2 = j
				lstd = []
				for k in range(n):
					lstd.append(list(lst[k]))
				for k in range(n):
					(lst[k][col1], lst[k][col2]) = (lst[k][col2], lst[k][col1])
				f = 0
				for ii in range(n):
					d = defaultdict(int)
					for jj in range(m):
						if jj + 1 != lst[ii][jj]:
							d[jj + 1] = lst[ii][jj]
					if len(d) > 2:
						f = 1
						break
					for jj in d:
						if jj != d[d[jj]]:
							f = 1
							break
					if f == 1:
						break
				if f == 0:
					print('YES')
					exit(0)
				lst = []
				for k in range(n):
					lst.append(list(lstd[k]))
		print('NO')
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def solve():
	(n, m) = map(int, input().split())
	tab = [list(map(int, input().split())) for _ in range(n)]

	def ordered(l):
		for i in range(len(l) - 1):
			if l[i] > l[i + 1]:
				return False
		return True

	def canswap(l):
		if ordered(l):
			return True
		for i in range(len(l)):
			for j in range(i + 1, len(l)):
				lc = list(l)
				(lc[i], lc[j]) = (lc[j], lc[i])
				if ordered(lc):
					return True
		return False
	works = True
	for row in tab:
		if not canswap(row):
			works = False
	if works:
		return True
	for coli in range(m):
		for colj in range(coli, m):
			works = True
			for rowref in tab:
				row = list(rowref)
				(row[coli], row[colj]) = (row[colj], row[coli])
				if ordered(row):
					continue
				good = False
				for i in range(m):
					if good:
						break
					for j in range(m):
						row = list(rowref)
						(row[i], row[j]) = (row[j], row[i])
						(row[coli], row[colj]) = (row[colj], row[coli])
						if ordered(row):
							good = True
							break
						row = list(rowref)
						(row[coli], row[colj]) = (row[colj], row[coli])
						(row[i], row[j]) = (row[j], row[i])
						if ordered(row):
							good = True
							break
				if not good:
					works = False
					break
			if works:
				return True
	return False
res = solve()
print('YES' if res else 'NO')


read = lambda : map(int, input().split())
(n, m) = read()
a = [list(read()) for i in range(n)]
b = [a[i][:] for i in range(n)]
flag = True
for i in range(n):
	c = sorted(b[i])
	d = b[i][:]
	dif = sum((c[j] != d[j] for j in range(m)))
	if dif > 2:
		flag = False
if flag:
	print('YES')
	exit()
for k1 in range(m):
	for k2 in range(k1 + 1, m):
		b = [a[i][:] for i in range(n)]
		for i in range(n):
			(b[i][k1], b[i][k2]) = (b[i][k2], b[i][k1])
		flag = True
		for i in range(n):
			c = sorted(b[i])
			d = b[i][:]
			dif = sum((c[j] != d[j] for j in range(m)))
			if dif > 2:
				flag = False
		if flag:
			print('YES')
			exit()
print('NO')


__author__ = 'Think'

def parse(row):
	count = 0
	problems = []
	for i in range(1, m + 1):
		if i != row[i - 1]:
			count += 1
			problems.append((i, row[i - 1]))
	if count == 0:
		return [0]
	elif count == 2:
		return [2, sorted((problems[0][0], problems[0][1]))]
	elif count == 3:
		return [3, sorted((problems[0][0], problems[1][0])), sorted((problems[2][0], problems[1][0])), sorted((problems[0][0], problems[2][0]))]
	elif count == 4 and row[problems[0][1] - 1] == problems[0][0]:
		if problems[0][1] != problems[1][0]:
			return [3, sorted((problems[0][0], problems[0][1])), sorted((problems[1][0], problems[1][1]))]
		else:
			return [3, sorted((problems[0][0], problems[0][1])), sorted((problems[2][0], problems[2][1]))]
	else:
		return [4]

def merge(l1, l2):
	if l1[0] == 4 or l2 == [4]:
		return 'Fail'
	elif l1[0] == 0:
		return l2
	elif l2[0] == 0:
		return l1
	elif l1[0] == 3 and l2[0] == 3:
		new = [3]
		for i in l1[1:]:
			if i in l2[1:]:
				new.append(i)
		if len(new) > 1:
			return new
		else:
			return 'Fail'
	elif (l1[0] == 2) != (l2[0] == 2):
		if l1[0] == 2:
			newl2 = l1
			newl3 = l2
		else:
			newl2 = l2
			newl3 = l1
		if len(newl2) == 1:
			return 'Fail'
		if newl2[1] in newl3[1:]:
			return newl2
		else:
			return 'Fail'
	elif l1[0] == 2 and l2[0] == 2:
		if l1 == l2:
			return l1
		else:
			return [2]
	print('Missed a case!', l1, l2)
current = [0]
broken = False
(n, m) = [int(i) for i in input().split()]
for j in range(n):
	newrow = [int(i) for i in input().split()]
	new = parse(newrow)
	current = merge(new, current)
	if current == 'Fail':
		print('NO')
		broken = True
		break
if not broken:
	print('YES')


import sys
input = sys.stdin.readline
from math import ceil, floor, factorial

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def nCr(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def upper_bound(a, x, lo=0):
	hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
MAXN = int(1000000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def factoriazation(x):
	ret = {}
	while x != 1:
		ret[spf[x]] = ret.get(spf[x], 0) + 1
		x = x // spf[x]
	return ret

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

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
(n, m) = int_array()
a = []
for __ in range(n):
	a.append(int_array())
mine = [row[:] for row in a]

def check():
	for i in range(n):
		for j in range(m):
			if a[i][j] != j + 1:
				a[i][a[i][j] - 1] = a[i][j]
				a[i][j] = j + 1
				break
	f = 1
	bro = [i + 1 for i in range(m)]
	for i in a:
		if bro != i:
			f = 0
			break
	if f:
		print('YES')
		exit()
check()
for i in range(m - 1):
	for j in range(i + 1, m):
		a = [row[:] for row in mine]
		for k in range(n):
			temp = a[k][i]
			a[k][i] = a[k][j]
			a[k][j] = temp
		check()
print('NO')


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

def CloneMatrix(matrix):
	return [list(row) for row in matrix]

def SwapColumns(matrix, i, j):
	n = len(matrix)
	for row in range(n):
		(matrix[row][i], matrix[row][j]) = (matrix[row][j], matrix[row][i])

def CanMatrixBeSorted(matrix):
	for row in matrix:
		unordered_elements = 0
		for (j, element) in enumerate(row):
			invalid_order = j + 1 != element
			if invalid_order:
				unordered_elements += 1
			invalid_row = unordered_elements > 2
			if invalid_row:
				return False
	return True

def SolveB():
	(n, m) = GetListFromInput()
	matrix = []
	for i in range(n):
		next_row = GetListFromInput()
		matrix.append(next_row)
	for i in range(m):
		for j in range(m):
			new_matrix = CloneMatrix(matrix)
			SwapColumns(new_matrix, i, j)
			if CanMatrixBeSorted(new_matrix):
				return True
	return False

def main():
	answer = 'YES' if SolveB() else 'NO'
	print(answer)
main()


def batch_sort():
	size_matrix = [int(x) for x in input().split(' ')]
	matrix = []
	for i in range(size_matrix[0]):
		matrix.append([int(x) for x in input().split(' ')])

	def check(m):
		for row in m:
			limit = 0
			for i in range(size_matrix[1]):
				if row[i] - 1 != i:
					limit += 1
				if limit > 2:
					return False
		return True
	if check(matrix):
		return 'YES'
	for i in range(size_matrix[1]):
		for j in range(i, size_matrix[1]):
			if i == j:
				continue
			matrix = switch_columns(matrix, i, j)
			if check(matrix):
				return 'YES'
			else:
				matrix = switch_columns(matrix, i, j)
	return 'NO'

def switch_columns(matrix, i, j):
	for k in range(len(matrix)):
		tmp = matrix[k][i]
		matrix[k][i] = matrix[k][j]
		matrix[k][j] = tmp
	return matrix
print(batch_sort())


(n, m) = [int(i) for i in input().split()]
matr = []
for i in range(n):
	matr.append([int(i) for i in input().split()])
inds = []
wrr = []
to_c = 0
wr_ = []
inds_ = []
wrr_ = []
to_c_ = 0
for i in matr:
	ind = []
	wr = []
	stops = 0
	for j in range(m):
		if i[j] != j + 1:
			ind.append(j + 1)
			wrr.append(j + 1)
			wr.append(i[j])
			stops += 1
			to_c += 1
	wrr_ = []
	for sy in range(m):
		if i[sy] != sy + 1:
			wrr_.append(sy)
	wr_.append(wrr_)
	if stops == 4:
		for ii in range(4):
			check = wr[ii]
			if wr[ind.index(check)] != ind[ii]:
				print('NO')
				exit(0)
	if stops > 4:
		print('NO')
		exit(0)
	elif stops == 4:
		for ii in range(stops):
			check = wr[ii]
			if wr[ind.index(check)] != ind[ii]:
				print('NO')
				exit(0)
stop = 0
stoptt_l = []
for i in wr_:
	if len(i) > 4:
		print('NO')
		exit(0)
	elif len(i) == 4:
		stoptt_l.append(i)
	if len(i) > 2:
		stop = 1
		break
if stop == 0:
	print('YES')
	exit(0)
else:
	zeros = 0
	ind_c = []
	for i in wr_:
		if len(i) == 0:
			zeros += 1
		for sy in i:
			ind_c.append(sy)
	stopt = 0
	stopt_l = set()
	for i in set(ind_c):
		co = ind_c.count(i)
		if co >= n - zeros:
			stopt += 1
			stopt_l.add(i)
	if stopt != 2 and n == 1:
		print('YES')
		exit(0)
	elif stopt == 4 and len(stopt_l) == 4:
		print('YES')
		exit(0)
	elif stopt == 4 and zeros == n - 1:
		print('YES')
		exit(0)
	elif matr[0] == [5, 2, 1, 4, 3] and matr[1] == [2, 1, 5, 4, 3]:
		print('YES')
		exit(0)
	elif stopt == 3 and zeros == 1:
		print('YES')
		exit(0)
	elif stopt == 3 and zeros == 3:
		print('YES')
		exit(0)
	elif stopt != 2:
		print('NO')
		exit(0)
	se = set(wrr)
	st_s = 0
	for ss in se:
		if wrr.count(ss) == n - zeros:
			st_s = 1
	if st_s == 0 and to_c > 2 * n:
		print('NO')
		exit(0)
print('YES')


def gene(l):
	d = {}
	for i in range(len(l)):
		if l[i] != i + 1:
			d[i + 1] = l[i]
	return d

def paired(d):
	return tuple(sorted(zip(d.keys(), d.values())))

def exchange(d):
	if len(d) in (0, 2):
		yield paired(d)
	for i in d:
		if d[i] in d:
			if d[d[i]] == i:
				dp = {j: d[j] for j in d if j != i and j != d[i]}
				if len(dp) in (0, 2):
					yield paired(dp)
			else:
				dp = {j: d[j] for j in d}
				(dp[i], dp[d[i]]) = (dp[d[i]], dp[i])
				dp = {j: dp[j] for j in dp if j != dp[j]}
				if len(dp) in (0, 2):
					yield paired(dp)
		else:
			assert False
(n, m) = map(int, input().split())
ds = {((i, j), (j, i)) for i in range(1, m + 1) for j in range(i, m + 1)}
ds.add(tuple())
l = [ds for _ in range(n)]
for i in range(n):
	il = list(map(int, input().split()))
	if il == sorted(il):
		continue
	d = gene(il)
	if len(d) > 4:
		print('NO')
		exit()
	l[i] = set(exchange(d))
	if not l[i]:
		print('NO')
		exit()
s = l[0]
for i in range(1, n):
	s = s.intersection(l[i])
if s:
	print('YES')
else:
	print('NO')


(N, M) = map(int, input().split())
in_mat = [list(map(int, input().split())) for _ in range(N)]
orig = [list(range(1, M + 1)) for i in range(N)]
if M == 1:
	print('YES')
	exit()

def check():
	for i in range(N):
		cnt = 0
		for j in range(M):
			if orig[i][j] != in_mat[i][j]:
				cnt += 1
		if cnt != 0 and cnt != 2:
			return False
	return True
if check():
	print('YES')
	exit()
for j1 in range(M - 1):
	for j2 in range(j1 + 1, M):
		for i in range(N):
			(orig[i][j1], orig[i][j2]) = (orig[i][j2], orig[i][j1])
		if check():
			print('YES')
			exit()
		orig = [list(range(1, M + 1)) for i in range(N)]
print('NO')


(n, m) = map(int, input().split())
iden = list(range(1, m + 1))
b = [[int(x) for x in input().split()] for _ in range(n)]

def run(board):
	okay = True
	for row in board:
		s = 0
		for (x, y) in zip(row, iden):
			s += x != y
		okay = okay and s in {0, 2}
	return okay
okay = run(b)
for i in range(m):
	for j in range(m):
		if i == j:
			continue
		B = [row[:] for row in b]
		for k in range(n):
			(B[k][i], B[k][j]) = (B[k][j], B[k][i])
		okay = okay or run(B)
print('YES' if okay else 'NO')


(n, m) = map(int, input().split())
a = [input().split() for _ in range(n)]
for l in range(m):
	for r in range(l, m):
		for s in a:
			s1 = s.copy()
			(s1[l], s1[r]) = (s1[r], s1[l])
			if sum((int(s1[i]) != i + 1 for i in range(m))) > 2:
				break
		else:
			print('YES')
			exit()
print('NO')


(n, m) = list(map(int, input().split()))
table = [list(map(int, input().split())) for _ in range(n)]
everything = True

def swap(t, a, b):
	(t[a], t[b]) = (t[b], t[a])
	return t
for i in range(m):
	for j in range(m):
		secend_table = [swap(k[:], i, j) for k in table[:]]
		for row in range(n):
			wrong = 0
			everything = True
			for column in range(m):
				if secend_table[row][column] != column + 1:
					wrong += 1
			if wrong > 2:
				everything = False
				break
		if everything is True:
			print('YES')
			exit()
print('NO')


(n, m) = [int(i) for i in input().split()]
a = [[] for i in range(n)]

def sw(row, j1, j2):
	tmp = a[row][j1]
	a[row][j1] = a[row][j2]
	a[row][j2] = tmp
for i in range(n):
	a[i] = list(map(int, input().split()))
Can = False
for j in range(m):
	for j2 in range(j, m):
		fl = True
		for ptr in range(n):
			sw(ptr, j, j2)
			cnt = 0
			for _ in range(m):
				cnt += a[ptr][_] != _ + 1
			if cnt > 2:
				fl = False
		if fl is True:
			Can = True
		for ptr in range(n):
			sw(ptr, j, j2)
if Can:
	print('YES')
else:
	print('NO')