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: competition

Starter code:

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


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

read = lambda: list(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')
            return
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')
            return
print('NO')


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




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


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):
    # print(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]
    # print(arr_)
    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:
            # print(row, 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()

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 = 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')




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


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')
else:
    if 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')
                else:
                    if 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 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
#         for k in range(n):
#             print(a[k], f(k))
#         print()
        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")

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()

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, 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')
# print(need_one_or_zero_swap([1, 4, 3, 2]))


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

__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")


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 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(list(d.keys()), list(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 = list(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)
    # print(d)
    if len(d) > 4:
        print('NO')
        return
    l[i] = set(exchange(d))
    if not l[i]:
        print('NO')
        return
#print(l)

s = l[0]
for i in range(1, n):
    s = s.intersection(l[i])
# print(s)
if s:
    print('YES')
else:
    print('NO')


read = lambda: list(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')
    return
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')
            return
print('NO')


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
#print('swaps:')
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
    #print(swaps)
    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)

#print('possible:', possible, 'p:', p, 'col_swap:', col_swap)
if possible and col_swap and p:
    c = set(p[0])
    for x in p:
        c = c.intersection(x)
    possible = bool(c)
    #print('c:', c)

if possible:
    print('YES')
else:
    print('NO')

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)

n, m = 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')

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