You are given a grid with $n$ rows and $m$ columns, where each cell has a positive integer written on it. Let's call a grid good, if in each row the sequence of numbers is sorted in a non-decreasing order. It means, that for each $1 \le i \le n$ and $2 \le j \le m$ the following holds: $a_{i,j} \ge a_{i, j-1}$.

You have to to do the following operation exactly once: choose two columns with indexes $i$ and $j$ (not necessarily different), $1 \le i, j \le m$, and swap them.

You are asked to determine whether it is possible to make the grid good after the swap and, if it is, find the columns that need to be swapped.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of rows and columns respectively.

Each of the next $n$ rows contains $m$ integers, $j$-th element of $i$-th row is $a_{i,j}$ ($1 \le a_{i,j} \le 10^9$) — the number written in the $j$-th cell of the $i$-th row.

It's guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

If after the swap it is impossible to get a good grid, output $-1$.

In the other case output $2$ integers — the indices of the columns that should be swapped to get a good grid.

If there are multiple solutions, print any.


-----Examples-----

Input
5
2 3
1 2 3
1 1 1
2 2
4 1
2 3
2 2
2 1
1 1
2 3
6 2 1
5 4 3
2 1
1
2
Output
1 1
-1
1 2
1 3
1 1


-----Note-----

In the first test case the grid is initially good, so we can, for example, swap the first column with itself.

In the second test case it is impossible to make the grid good.

In the third test case it is needed to swap the first and the second column, then the grid becomes good.

Difficulty: MEDIUM
Tags: Constructive algorithms

Sorting

Implementation

Greedy algorithms

Complete search
Skill types: Complete search

Sorting

Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def solve():
	(N, M) = list(map(int, input().split()))
	X = []
	for i in range(M):
		X.append([])
	for i in range(N):
		K = list(map(int, input().split()))
		for j in range(M):
			X[j].append(K[j])
	flag = 0
	ans = set()
	Y = X.copy()
	for i in range(N):
		if flag:
			break
		for j in range(1, M):
			if X[j - 1][i] > X[j][i]:
				X.sort(key=lambda x: x[i])
				for l in range(M):
					if X[l][i] != Y[l][i]:
						ans.add(l + 1)
				continue
	for i in range(N):
		for j in range(1, M):
			if X[j - 1][i] > X[j][i]:
				print(-1)
				return
	if len(ans) == 0:
		print(1, 1)
	elif len(ans) >= 3:
		print(-1)
	else:
		print(*ans)
for _ in range(int(input())):
	solve()


T = int(input())
for case in range(T):
	(n, m) = map(int, input().split())
	g = [tuple(map(int, input().split())) for r in range(n)]
	g = tuple(zip(*g))
	r = tuple(sorted(g))
	for i in range(1, m):
		for j in range(n):
			if r[i][j] < r[i - 1][j]:
				break
		else:
			continue
		print(-1)
		break
	else:
		d = []
		for i in range(m):
			if g[i] != r[i]:
				d.append(i)
		if len(d) == 0:
			print(1, 1)
		elif len(d) == 2:
			print(d[0] + 1, d[1] + 1)
		else:
			print(-1)


for case in range(int(input())):
	(n, m) = map(int, input().split())
	arr = [list(map(int, input().split())) for _ in range(n)]
	if m == 1:
		print(1, 1)
	else:
		swap = set()
		not_possible = False
		for i in range(n):
			temp = sorted(arr[i])
			for j in range(m):
				if temp[j] != arr[i][j]:
					swap.add(j)
			if not_possible:
				break
		swap = list(swap)
		if swap:
			for row in arr:
				temp_row = row
				(temp_row[swap[0]], temp_row[swap[1]]) = (temp_row[swap[1]], temp_row[swap[0]])
				if temp_row != sorted(row):
					not_possible = True
					break
		for i in range(n):
			for j in range(1, m):
				if arr[i][j - 1] > arr[i][j]:
					not_possible = True
					break
			if not_possible:
				break
		if not_possible:
			print(-1)
		else:
			print(' '.join((str(n + 1) for n in swap)) if swap else '1 1')


import sys
input = sys.stdin.readline
ints = lambda : list(map(int, input().split()))
t = ints()[-1]
for _ in range(t):
	(n, m) = ints()
	grid = [ints() for _ in range(n)]
	problem = set()
	for row in grid:
		temp = row[:]
		temp.sort()
		for i in range(m):
			if temp[i] != row[i]:
				problem.add(i)
	problem = list(problem)
	if len(problem) == 0:
		print(1, 1)
	elif len(problem) > 2:
		print(-1)
	else:
		is_possible = True
		for i in range(n):
			(grid[i][problem[0]], grid[i][problem[1]]) = (grid[i][problem[1]], grid[i][problem[0]])
			for j in range(1, m):
				if grid[i][j] < grid[i][j - 1]:
					is_possible = False
		if not is_possible:
			print(-1)
		else:
			print(problem[0] + 1, problem[1] + 1)


def main():
	tc = int(input())
	for _ in range(tc):
		(n, m) = map(int, input().split())
		grid = [tuple(map(int, input().split())) for i in range(n)]
		grid = tuple(zip(*grid))
		new_grid = tuple(sorted(grid))
		for i in range(1, m):
			for j in range(n):
				if new_grid[i][j] < new_grid[i - 1][j]:
					break
			else:
				continue
			print(-1)
			break
		else:
			bad = []
			for i in range(m):
				if grid[i] != new_grid[i]:
					bad.append(i)
			k = len(bad)
			if k == 0:
				print(1, 1)
			elif k == 2:
				print(bad[0] + 1, bad[1] + 1)
			else:
				print(-1)
main()


iT = int(input())
for _ in range(iT):
	answer = ''
	(iN, iM) = map(int, input().split())
	lst_temp = [[] for _ in range(iN)]
	for idx in range(iN):
		lst_temp[idx] = list(map(int, input().split()))
	row = 0
	idx1 = -1
	for j in range(1, iM):
		for i in range(iN):
			if lst_temp[i][j] < lst_temp[i][j - 1] and idx1 == -1:
				idx1 = j
				row = i
				break
	if idx1 == -1:
		answer = '1 1'
	else:
		lst_temp_sot = sorted(lst_temp[row])
		idx2 = -1
		val = 0
		for i in range(iM):
			if lst_temp_sot[i] != lst_temp[row][i]:
				idx2 = i
				val = lst_temp_sot[i]
				break
		for i in range(iM):
			if lst_temp[row][i] == val:
				idx1 = i
		for idx in range(iN):
			temp = lst_temp[idx][idx2]
			lst_temp[idx][idx2] = lst_temp[idx][idx1]
			lst_temp[idx][idx1] = temp
		T_F = True
		for j in range(1, iM):
			for i in range(iN):
				if lst_temp[i][j] < lst_temp[i][j - 1]:
					T_F = False
					break
		if T_F:
			answer = f'{idx2 + 1} {idx1 + 1}'
		else:
			answer = '-1'
	print(answer)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	grid = []
	for i in range(n):
		grid.append([int(x) for x in input().split()])

	def solve(grid):
		(x, y) = (-2, -2)
		for i in range(n):
			k = 0
			for j in range(1, m):
				if grid[i][j] < grid[i][k]:
					if x == -2:
						x = k
					y = j
				if grid[i][j] > grid[i][j - 1]:
					k = j
		return [x, y]
	curr = solve(grid)
	(a, b) = (curr[0], curr[1])

	def exec(a, b, grid):
		if a == -1 and b == -1:
			return [-1]
		if a == -2 and b == -2:
			return [1, 1]
		for i in range(n):
			(grid[i][a], grid[i][b]) = (grid[i][b], grid[i][a])
			for j in range(1, m):
				if grid[i][j] < grid[i][j - 1]:
					return [-1]
		return [min(a, b) + 1, max(a, b) + 1]
	print(*exec(a, b, grid))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	arr = []
	for i in range(n):
		a = list(map(int, input().split()))
		arr.append(a)
	a = []
	for i in range(n):
		b = sorted(arr[i])
		for j in range(m):
			if arr[i][j] != b[j]:
				a.append(j)
		if a:
			break
	if len(a) > 2:
		print(-1)
	elif len(a) == 0:
		print(1, 1)
	else:
		for i in range(n):
			(arr[i][a[0]], arr[i][a[1]]) = (arr[i][a[1]], arr[i][a[0]])
		found = False
		for i in range(n):
			for j in range(1, m):
				if arr[i][j] < arr[i][j - 1]:
					print(-1)
					found = True
					break
			if found:
				break
		else:
			a = [a[0] + 1, a[1] + 1]
			print(*a, sep=' ')


T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	matrix = [None] * n
	for i in range(n):
		matrix[i] = list(map(int, input().split()))
	swap1 = -1
	swap2 = -1
	found = False
	for i in range(n):
		for j in range(m - 1):
			if matrix[i][j] > matrix[i][j + 1]:
				swap1 = j
				cur = int(matrix[i][j])
				while swap1 >= 0 and matrix[i][swap1] == cur:
					swap1 -= 1
				swap1 += 1
				for k in range(j + 1, m - 1):
					if matrix[i][k] > matrix[i][k + 1]:
						swap2 = k + 1
						break
				if swap2 == -1:
					for k in range(j + 1, m - 1):
						if matrix[i][k] < matrix[i][k + 1]:
							swap2 = k
							break
				if swap2 == -1:
					swap2 = m - 1
				found = True
				break
		if found:
			break
	if not found:
		print('1 1')
	else:
		ans = True
		for i in range(n):
			temp = matrix[i][swap1]
			matrix[i][swap1] = matrix[i][swap2]
			matrix[i][swap2] = temp
		for i in range(n):
			for j in range(m - 1):
				if matrix[i][j] > matrix[i][j + 1]:
					ans = False
					break
			if not ans:
				break
		if not ans:
			print(-1)
		else:
			print(str(swap1 + 1) + ' ' + str(swap2 + 1))


test_cases = int(input())

def in_order(row):
	for i in range(1, len(row)):
		if row[i] < row[i - 1]:
			return False
	return True

def diff_indices(a, b):
	indices = []
	for i in range(len(a)):
		if a[i] != b[i]:
			indices.append(i)
	return indices
for test in range(test_cases):
	nums = [int(num) for num in input().strip().split()]
	(rows, cols) = nums
	grid = []
	for row in range(rows):
		line = [int(num) for num in input().strip().split()]
		grid.append(line)
	row_out_order = -1
	for (r, row) in enumerate(grid):
		if not in_order(row):
			row_out_order = r
			break
	if row_out_order == -1:
		print(1, 1)
	else:
		sorted_row_out_order = sorted(grid[row_out_order])
		diff_cols = diff_indices(grid[row_out_order], sorted_row_out_order)
		if len(diff_cols) != 2:
			print(-1)
		else:
			(col1, col2) = diff_cols
			all_in_order = True
			for row in grid:
				(row[col1], row[col2]) = (row[col2], row[col1])
				if not in_order(row):
					all_in_order = False
					break
			if all_in_order:
				print(col1 + 1, col2 + 1)
			else:
				print(-1)


import math
import random
import sys

def test():
	(n, m) = [int(x) for x in input().split()]
	a = [list(map(int, input().split())) for i in range(n)]
	swap = []
	for i in range(n):
		b = sorted(a[i])
		for j in range(m):
			if a[i][j] != b[j]:
				swap.append(j)
		if len(swap) > 0:
			break
	if len(swap) == 0:
		print(1, 1)
		return
	if len(swap) > 2:
		print(-1)
		return
	for i in range(n):
		tem = a[i][swap[0]]
		a[i][swap[0]] = a[i][swap[1]]
		a[i][swap[1]] = tem
		if sorted(a[i]) != a[i]:
			print('-1')
			return
	print(swap[0] + 1, swap[1] + 1)
t = int(input())
for i in range(t):
	test()


def check(grid, u, v):
	for irow in grid:
		sirow = list(irow)
		(sirow[u], sirow[v]) = (sirow[v], sirow[u])
		for jc in range(1, len(sirow)):
			if sirow[jc - 1] > sirow[jc]:
				return False
	return True

def solve():
	(n, m) = map(int, input().split())
	grid = []
	for i in range(n):
		row = list(map(int, input().split()))
		grid.append(row)
	(u, v) = (-1, -1)
	for row in grid:
		sorted_row = sorted(row)
		for j in range(m):
			if row[j] == sorted_row[j]:
				continue
			if v == -1:
				v = j
			elif u == -1:
				u = j
			else:
				v = u = -2
		if v == -2:
			print('-1')
			return
		if v == -1:
			continue
		if check(grid, u, v):
			print(v + 1, u + 1)
			return
		print('-1')
		return
	print('1 1')
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append([int(i) for i in input().split()])
	ans = []
	f = 0
	for i in l:
		if i != sorted(i):
			ans.append(i)
			if len(ans) == 2:
				break
	ind = []
	for i in range(len(ans)):
		one = ans[i]
		two = sorted(one)
		ind = []
		for i in range(len(one)):
			if one[i] != two[i]:
				ind.append(i)
	if len(ind) == 2:
		for i in range(len(l)):
			(l[i][ind[0]], l[i][ind[1]]) = (l[i][ind[1]], l[i][ind[0]])
	for i in l:
		if i != sorted(i):
			f = 1
	if f == 1:
		print('-1')
	else:
		try:
			print(ind[0] + 1, 1 + ind[1])
		except:
			print(1, 1)


def check(list):
	ans = True
	for i in range(len(list) - 1):
		if list[i] > list[i + 1]:
			ans = False
			break
	return ans

def index(list):
	temp = sorted(list)
	val = []
	for i in range(len(list)):
		if list[i] != temp[i]:
			val.append(i)
	return val
t = int(input())
for q in range(t):
	(n, m) = [int(x) for x in input().split()]
	grid = []
	for c in range(n):
		row = [int(x) for x in input().split()]
		grid.append(row)
	(nature, corr) = (True, -1)
	for d in range(n):
		if not check(grid[d]):
			nature = False
			corr = d
			break
	if nature:
		print(1, 1)
	elif len(index(grid[corr])) != 2:
		print(-1)
	else:
		o = index(grid[corr])[0]
		p = index(grid[corr])[1]
		ultimate = True
		for j in range(n):
			(grid[j][o], grid[j][p]) = (grid[j][p], grid[j][o])
			if not check(grid[j]):
				ultimate = False
				break
		if ultimate:
			print(o + 1, p + 1)
		else:
			print(-1)


t = int(input())
while t:
	(n, m) = map(int, input().split())
	l = []
	flag = 1
	key = -1
	for i in range(n):
		ll = list(map(int, input().split()))
		l.append(ll)
	for i in range(n):
		lo = sorted(l[i])
		if lo != l[i]:
			key = i
			break
	c = 0
	lt = sorted(l[key])
	li = []
	for i in range(m):
		if l[key][i] != lt[i]:
			c += 1
			li.append(i)
		if c > 2:
			flag = 0
			break
	if key == -1:
		li.append(0)
		li.append(0)
	elif flag:
		for i in range(n):
			(l[i][li[0]], l[i][li[-1]]) = (l[i][li[-1]], l[i][li[0]])
			lp = sorted(l[i])
			if lp != l[i]:
				flag = 0
				break
	if flag:
		print(li[0] + 1, li[-1] + 1)
	else:
		print(-1)
	t -= 1


class Solve:

	def __init__(self):
		(self.n, self.m) = map(int, input().strip().split())
		self.table = [list(map(int, input().strip().split())) for _ in range(self.n)]

	def check_table(self):
		for i in range(self.n):
			for j in range(1, self.m):
				if self.table[i][j] < self.table[i][j - 1]:
					return i
		return None

	def solve(self):
		row = self.check_table()
		si = None
		sj = None
		if row is not None:
			sorted_row = sorted(self.table[row])
			for i in range(self.m):
				if sorted_row[i] != self.table[row][i]:
					if si is None:
						si = i
					else:
						sj = i
		if si is None:
			si = sj = 0
		for i in range(self.n):
			(self.table[i][si], self.table[i][sj]) = (self.table[i][sj], self.table[i][si])
		if self.check_table() is not None:
			print(-1)
		else:
			print(si + 1, sj + 1)

def main():
	t = int(input().strip())
	for i in range(t):
		Solve().solve()
main()


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	A = [[int(c) for c in input().split()] for _ in range(N)]
	swappos = []
	for i in range(N):
		B = sorted(A[i])
		for j in range(M):
			if B[j] != A[i][j]:
				swappos.append(j)
		if len(swappos) > 0:
			break
	if len(swappos) == 0:
		print('1 1')
		continue
	if len(swappos) > 2:
		print(-1)
		continue
	good = True
	for i in range(N):
		(A[i][swappos[0]], A[i][swappos[1]]) = (A[i][swappos[1]], A[i][swappos[0]])
		for j in range(M - 1):
			if A[i][j] > A[i][j + 1]:
				good = False
				break
		if not good:
			break
	if good:
		print(f'{swappos[0] + 1} {swappos[1] + 1}')
	else:
		print(-1)


t = int(input())
for i in range(t):
	(n, m) = input().split(' ')
	(n, m) = (int(n), int(m))
	a = [[] * m] * n
	for j in range(n):
		a[j] = input().split(' ')
		for k in range(m):
			a[j][k] = int(a[j][k])
	x = 0
	y = 0
	for j in range(n):
		if a[j] == sorted(a[j]):
			x += 1
		else:
			y = j
	if x == n:
		print('1 1')
		continue
	b = sorted(a[y])
	c = []
	for j in range(m):
		if a[y][j] != b[j]:
			c.append(j)
	if len(c) > 2:
		print('-1')
		continue
	f = 0
	for j in range(n):
		aux = a[j][c[0]]
		a[j][c[0]] = a[j][c[1]]
		a[j][c[1]] = aux
		if a[j] != sorted(a[j]):
			print('-1')
			f = 1
			break
	if f == 0:
		print(c[0] + 1, c[1] + 1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	w = 0
	(p, o) = (-1, -1)
	for i in range(n):
		t = list(map(int, input().split()))
		u = t.copy()
		u.sort()
		if t == u:
			w += 1
		l.append(t)
	if w == n:
		print(1, 1)
	else:
		for i in range(len(l)):
			k = l[i]
			u = k.copy()
			u.sort()
			for i in range(len(k)):
				if u[i] != k[i]:
					if p == -1:
						p = i
					elif o == -1:
						o = i
				else:
					continue
		t = 0
		for i in range(len(l)):
			k = l[i]
			u = k.copy()
			k.sort()
			(u[p], u[o]) = (u[o], u[p])
			if u == k:
				continue
			else:
				t += 1
				break
		if t > 0:
			print(-1)
		else:
			print(p + 1, o + 1)


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	(n, m) = map(int, input().split())
	A = [list(map(int, input().split())) for i in range(n)]
	flag = 1
	ANS = []
	for i in range(n):
		if flag == 0 or len(ANS) > 0:
			break
		B = list(A[i])
		C = list(A[i])
		for j in range(1, m):
			C[j] = max(C[j - 1], C[j])
		for j in range(m - 1, -1, -1):
			if B[j] < C[j]:
				for k in range(m):
					if B[k] > B[j]:
						A1 = [k, j]
						break
				(x, y) = A1
				(B[x], B[y]) = (B[y], B[x])
				if sorted(B) == B:
					ANS.append((x, y))
				else:
					flag = 0
				break
	if flag == 0:
		print(-1)
		continue
	if len(ANS) == 0:
		print(1, 1)
		continue
	(x, y) = ANS[0]
	for i in range(n):
		B = A[i]
		(B[x], B[y]) = (B[y], B[x])
		if sorted(B) == B:
			True
		else:
			flag = 0
			break
	if flag == 1:
		print(x + 1, y + 1)
	else:
		print(-1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mat = [[int(x) for x in input().split()] for i in range(n)]
	res = set()
	for i in range(n):
		b = sorted(mat[i])
		t = []
		for j in range(m):
			if b[j] != mat[i][j]:
				t.append(j + 1)
		if t:
			res.add(tuple(t))
	if len(res) > 1:
		print(-1)
	elif not res:
		print(1, 1)
	else:
		t = res.pop()
		if len(t) == 2:
			(l, r) = t
			for i in range(n):
				(mat[i][l - 1], mat[i][r - 1]) = (mat[i][r - 1], mat[i][l - 1])
			flag = True
			for i in range(n):
				if not flag:
					break
				for j in range(1, m):
					if mat[i][j] < mat[i][j - 1]:
						flag = False
						break
			if flag:
				print(l, r)
				continue
		print(-1)


def dif_col(l):
	new = l[:]
	new.sort()
	distinct = set()
	for i in range(len(l)):
		if l[i] != new[i]:
			distinct.add(i)
	return distinct

def check_changed(l, swap):
	(a, b) = (swap[0], swap[1])
	(l[a], l[b]) = (l[b], l[a])
	for i in range(len(l) - 1):
		if l[i] > l[i + 1]:
			return False
	return True
case = int(input())
for _ in range(case):
	q = input().split()
	n = int(q[0])
	m = int(q[1])
	board = []
	for row in range(n):
		new = input().split()
		board.append([int(elem) for elem in new])
	found = None
	for row in board:
		if found:
			break
		else:
			to_change = dif_col(row)
			if len(to_change) == 0:
				continue
			elif len(to_change) >= 3:
				found = (1, 1)
				break
			else:
				found = tuple(to_change)
	if found:
		wrong = False
		for i in range(n):
			if not check_changed(board[i], found):
				print(-1)
				wrong = True
				break
		if not wrong:
			print(found[0] + 1, found[1] + 1)
	else:
		print(1, 1)


t = int(input())
for i in range(t):
	(a, b) = input().split()
	(n, m) = (int(a), int(b))
	c = [[] * m] * n
	e = []
	flag = 0
	ans = 0
	tot = 0
	for j in range(n):
		c[j] = input().split()
		for k in range(m):
			c[j][k] = int(c[j][k])
	for j in range(n):
		if c[j] == sorted(c[j]):
			ans += 1
		else:
			tot = j
	if ans == n:
		print('1 1')
		continue
	d = sorted(c[tot])
	for j in range(m):
		if c[tot][j] != d[j]:
			e.append(j)
	if len(e) > 2:
		print('-1')
		continue
	for j in range(n):
		temp = c[j][e[0]]
		c[j][e[0]] = c[j][e[1]]
		c[j][e[1]] = temp
		if c[j] != sorted(c[j]):
			print('-1')
			flag = 1
			break
	if flag == 0:
		print(e[0] + 1, e[1] + 1)


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	s = []
	for i in range(m):
		s.append(list(map(int, input().split())))
	h = set()
	flag = False
	for i in range(m):
		row = sorted(s[i])
		for j in range(n):
			if row[j] != s[i][j]:
				h.add(j + 1)
				if len(h) > 2:
					flag = True
					break
		if flag:
			break
	if flag:
		print('-1')
	elif len(h) == 0:
		print('1 1')
	else:
		(x, y) = (min(h) - 1, max(h) - 1)
		for i in range(m):
			if s[i][x] < s[i][y]:
				print(-1)
				break
		else:
			print(x + 1, y + 1)


T = int(input())
while T:
	T -= 1
	(n, m) = map(int, input().split())
	ex = []
	a = [[0]] * n
	for i in range(n):
		a[i] = list(map(int, input().split()))
	for row in a:
		rc = row.copy()
		rc.sort()
		for i in range(m):
			if row[i] != rc[i]:
				ex.append(i)
		if len(ex):
			break
	if len(ex) == 0:
		print(1, 1)
	elif len(ex) == 2:
		(c1, c2) = ex
		flag = True
		for row in a:
			(row[c1], row[c2]) = (row[c2], row[c1])
			for i in range(1, m):
				if row[i] < row[i - 1]:
					flag = False
					break
			if not flag:
				break
		if flag:
			print(c1 + 1, c2 + 1)
		else:
			print(-1)
	else:
		print(-1)


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	(n, m) = map(int, input().split())
	mat = []
	for i in range(n):
		a = list(map(int, input().split()))[:m]
		mat.append(a)
	k = 0
	(one, two) = (0, 0)
	for row in range(n):
		A = mat[row]
		if len(set(A)) == 1:
			continue
		b = sorted(A)
		flag = 0
		(one, two) = (0, 0)
		for i in range(m):
			if b[i] != A[i]:
				flag += 1
				if flag == 1:
					one = i
				elif flag == 2:
					two = i
				else:
					print(-1)
					return
		if flag != 0:
			break
		k = row
	check = mat[k]
	if check[one] < check[two]:
		print(-1)
		return
	for i in range(k + 1, n):
		ok = mat[i]
		if ok[one] < ok[two]:
			print(-1)
			return
		g = sorted(ok)
		(ok[one], ok[two]) = (ok[two], ok[one])
		if g != ok:
			print(-1)
			return
	print(one + 1, two + 1)
t = int(input())
while t != 0:
	solve()
	t -= 1


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		l = list(map(int, input().split()))
		arr.append(l)
	flag = True
	indexs = []
	for i in range(n):
		ol = arr[i].copy()
		sl = arr[i].copy()
		sl.sort()
		ti = []
		li = 0
		for j in range(m):
			if ol[j] != sl[j]:
				ti.append(j)
				li += 1
		if li == 0:
			continue
		elif li == 2:
			indexs.append(tuple(ti))
		else:
			flag = False
			break
	if flag:
		li = len(indexs)
		if li == 0:
			print('1 1')
		else:
			s = set(indexs)
			ls = len(s)
			if ls == 1:
				l = s.pop()
				(p1, p2) = (l[0], l[1])
				flag1 = True
				for i in range(n):
					if arr[i][p1] < arr[i][p2]:
						flag1 = False
						break
				if flag1:
					print(p1 + 1, p2 + 1)
				else:
					print(-1)
			else:
				print(-1)
	else:
		print(-1)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	d = []
	for j in range(n):
		A = [int(k) for k in input().split()]
		d.append(A)
	flag = 0
	ans = []
	for j in d:
		b = j.copy()
		b.sort()
		a = []
		for h in range(m):
			if b[h] != j[h]:
				a.append(h)
		if len(a) > 2:
			flag = 1
			break
		elif len(a) == 2:
			ans.append((a[0], a[1]))
			break
	if flag == 1:
		print(-1)
	else:
		f = -1
		for r in ans:
			if r != (-1, -1):
				f = r
				break
		if f == -1:
			print(1, 1)
		else:
			l = f[0]
			r = f[1]
			a = 0
			for j in range(n):
				(d[j][l], d[j][r]) = (d[j][r], d[j][l])
			for j in range(n):
				for k in range(1, m):
					if d[j][k] < d[j][k - 1]:
						a = 1
						break
				if a == 1:
					break
			if a == 1:
				print(-1)
			else:
				print(l + 1, r + 1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lst = []
	for i in range(n):
		lst.append([int(x) for x in input().split()])
	idx = []
	for i in range(n):
		b = lst[i]
		d = sorted(lst[i])
		for j in range(m):
			if b[j] != d[j]:
				idx.append(j)
		if len(idx) != 0:
			break
	if len(idx) == 0:
		print(1, 1)
	elif len(idx) == 2:
		for i in range(n):
			(lst[i][idx[0]], lst[i][idx[1]]) = (lst[i][idx[1]], lst[i][idx[0]])
		flag = True
		for i in range(n):
			b = lst[i]
			d = sorted(b)
			if b != d:
				print(-1)
				flag = False
				break
		if flag:
			print(idx[0] + 1, idx[1] + 1)
	else:
		print(-1)


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	grid = []
	for i in range(m):
		grid.append(list(map(int, input().split())))
	a = set()
	f = False
	for i in range(m):
		arr = sorted(grid[i])
		for j in range(n):
			if arr[j] != grid[i][j]:
				a.add(j)
				if len(a) > 2:
					f = True
					break
		if f:
			break
	if f:
		print(-1)
	else:
		if not a:
			print(1, 1)
			continue
		(p, q) = (min(a), max(a))
		for i in range(m):
			if grid[i][p] < grid[i][q]:
				f = True
				break
		if f:
			print(-1)
		else:
			print(p + 1, q + 1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = [list(map(int, input().split())) for i in range(n)]
	swap = set()
	for row in arr:
		for (i, a, b) in zip(list(range(m)), row, sorted(row)):
			if a != b:
				swap.add(i + 1)
	if len(swap) > 2:
		print(-1)
	elif len(swap) == 2:
		swap = list(swap)
		y = 1
		for i in range(n):
			(arr[i][swap[0] - 1], arr[i][swap[1] - 1]) = (arr[i][swap[1] - 1], arr[i][swap[0] - 1])
			if sorted(arr[i]) != arr[i]:
				y = 0
		if y:
			print(*swap)
		else:
			print(-1)
	else:
		print(1, 1)


n = int(input())

def swap(arr, i, j):
	tmp = arr[i]
	arr[i] = arr[j]
	arr[j] = tmp
for i in range(n):
	(r, c) = map(int, input().split())
	matrix = []
	result = 0
	for j in range(r):
		row = list(map(int, input().split()))
		matrix.append(row)
	swap_i = -1
	swap_j = -1
	for k in range(r):
		row = matrix[k]
		sorted_row = row.copy()
		sorted_row.sort()
		for m in range(c):
			if row[m] != sorted_row[m]:
				if swap_i == -1:
					swap_i = m
				else:
					swap_j = m
					break
		if swap_i != -1:
			break
	if swap_i == -1:
		print(1, 1)
		continue
	for k in range(r):
		row = matrix[k]
		swap(row, swap_i, swap_j)
		sorted_row = row.copy()
		sorted_row.sort()
		for m in range(c):
			if row[m] != sorted_row[m]:
				result = -1
				break
		if result == -1:
			break
	if result == -1:
		print(-1)
	else:
		print(swap_i + 1, swap_j + 1)


def solve(arr):
	bad = []
	for i in range(len(arr)):
		b = list(arr[i])
		b.sort()
		for j in range(len(b)):
			if arr[i][j] != b[j]:
				bad.append(j)
		if len(bad) > 0:
			break
	if len(bad) == 0:
		print(1, 1)
	elif len(bad) > 2:
		print(-1)
	else:
		for i in range(n):
			(arr[i][bad[0]], arr[i][bad[1]]) = (arr[i][bad[1]], arr[i][bad[0]])
		check = False
		for i in range(n):
			if arr[i] != sorted(arr[i]):
				check = True
				break
		if check:
			print(-1)
		else:
			print(bad[0] + 1, bad[1] + 1)
for i in range(int(input())):
	(n, m) = map(int, input().split())
	lis = []
	for i in range(n):
		lis.append(list(map(int, input().split())))
	solve(lis)


import collections
import math
import sys
from queue import PriorityQueue
from random import randint
RANDOM = randint(1, 10 ** 9)

def main(testnumber):
	(n, m) = map(int, input().split())
	need_to_check = []
	swapp = set()
	rows = []
	notOk = False
	for i in range(n):
		row = list(map(int, input().split()))
		rows.append(row)
		row_s = row[:]
		row_s = sorted(row_s)
		c = 0
		swp = []
		for j in range(m):
			if row_s[j] != row[j]:
				c += 1
				swp.append(j)
			if c > 2:
				break
		if c > 2:
			notOk = True
		if c == 2:
			swapp.add((swp[0], swp[1]))
		if c == 0:
			need_to_check.append(i)
	if notOk:
		print(-1)
		return
	if len(swapp) == 0:
		print(1, 1)
		return
	if len(swapp) == 1:
		e = swapp.pop()
		l = e[0]
		r = e[1]
		ok = True
		for i in need_to_check:
			row = rows[i]
			tmp = row[l]
			row[l] = row[r]
			row[r] = tmp
			if not all((row[j] <= row[j + 1] for j in range(m - 1))):
				ok = False
				break
		if ok:
			print(l + 1, r + 1)
			return
	print(-1)
t = int(input())
cnt = 1
while t > 0:
	main(cnt)
	cnt += 1
	t -= 1


t = int(input())
while t != 0:
	(r, c) = list(map(int, input().split(' ')))
	arr = []
	for i in range(r):
		r1 = list(map(int, input().split(' ')))
		arr.append(r1)
	bad = []
	for i in range(0, r):
		if bad:
			break
		k = arr[i].copy()
		k.sort()
		for j in range(0, c):
			if arr[i][j] != k[j]:
				bad.append(j)
	flag = False
	if len(bad) == 0:
		print(1, 1)
		t -= 1
		continue
	elif len(bad) > 2:
		print(-1)
		t -= 1
		continue
	else:
		for i in range(0, r):
			(arr[i][bad[0]], arr[i][bad[1]]) = (arr[i][bad[1]], arr[i][bad[0]])
		for i in range(0, r):
			for j in range(0, c - 1):
				if arr[i][j] > arr[i][j + 1]:
					print(-1)
					flag = True
					break
			if flag:
				break
	if not flag:
		print(bad[0] + 1, bad[1] + 1)
	t -= 1


cases = int(input())
for i in range(cases):
	good = True
	(r, c) = map(int, input().split())
	gaps = []
	mat = []
	for j in range(r):
		row = list(map(int, input().split()))
		mat.append(row)
	for j in range(r):
		gaps = []
		row = mat[j]
		sortedRow = sorted(row)
		for k in range(c):
			if row[k] != sortedRow[k]:
				gaps.append(k)
		if gaps:
			break
	if gaps:
		if len(gaps) != 2:
			print(-1)
		else:
			(a, b) = gaps
			for j in range(r):
				(mat[j][a], mat[j][b]) = (mat[j][b], mat[j][a])
				for k in range(c - 1):
					if mat[j][k] > mat[j][k + 1]:
						good = False
			if good:
				print(a + 1, b + 1)
			else:
				print(-1)
	else:
		print(1, 1)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	lst = []
	for j in range(n):
		lst1 = list(map(int, input().split()))
		lst.append(lst1)
	lst1 = []
	e = 0
	ind = []
	v = len(lst[0])
	for j in lst:
		lst3 = j.copy()
		lst3.sort()
		a = []
		for h in range(v):
			if lst3[h] != j[h]:
				a.append(h)
		if len(a) > 2:
			e += 1
			break
		elif len(a) == 2:
			ind.append((a[0], a[1]))
			break
	if e > 0:
		print(-1)
	else:
		f = -1
		for r in ind:
			if r != (-1, -1):
				f = r
				break
		if f == -1:
			print(1, 1)
		else:
			l = f[0]
			r = f[1]
			for q in lst:
				(q[l], q[r]) = (q[r], q[l])
			a = 0
			for q in lst:
				for w in range(1, v):
					if q[w] < q[w - 1]:
						a += 1
						break
				if a > 0:
					break
			if a == 0:
				print(l + 1, r + 1)
			else:
				print(-1)


import math

def findSwaps(row, length):
	sr = sorted(row)
	badCols = []
	for i in range(length):
		if row[i] != sr[i]:
			badCols.append(i)
	if len(badCols) < 2:
		return (None, None)
	return (badCols[0], badCols[1])
t = int(input())
for _ in range(t):
	l = input().split()
	(m, n) = (int(l[0]), int(l[1]))
	grid = []
	for _ in range(m):
		l = input().split()
		grid.append([int(x) for x in l])
	swaps = None
	for i in range(m):
		(l, r) = findSwaps(grid[i], n)
		if not l and (not r):
			continue
		swaps = (l, r)
		break
	if not swaps:
		print('1 1')
		continue
	flag = False
	for i in range(m):
		(grid[i][l], grid[i][r]) = (grid[i][r], grid[i][l])
		for j in range(1, n):
			if grid[i][j] < grid[i][j - 1]:
				flag = True
				break
		if flag:
			break
	print(l + 1, r + 1) if not flag else print('-1')


for u in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	l = []
	for i in range(n):
		l.append([int(x) for x in input().split()])
	temp = []
	for i in range(n):
		temp.append(sorted(l[i]))
	for i in range(n):
		if l[i] != temp[i]:
			break
	q = []
	for y in range(m):
		if l[i][y] != temp[i][y]:
			q.append(y)
	if len(q) > 2:
		print(-1)
	elif len(q) == 0:
		print(1, 1)
	else:
		for i in range(n):
			(l[i][q[0]], l[i][q[1]]) = (l[i][q[1]], l[i][q[0]])
		flag = 0
		for i in range(n):
			if l[i] != temp[i]:
				flag = 1
				break
		if flag == 1:
			print(-1)
		else:
			print(q[0] + 1, q[1] + 1)


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().strip().split()))
	swap_pos = None
	impossible = False
	arr = []
	for _ in range(n):
		row = list(map(int, input().strip().split()))
		sort_row = sorted(row)
		arr.append(row)
		pos = []
		for i in range(m):
			if row[i] != sort_row[i]:
				pos.append(i)
		if len(pos) > 2:
			impossible = True
		elif len(pos) == 2:
			swap_pos = pos
	if impossible:
		print(-1)
	elif swap_pos is None:
		print('1 1')
	else:
		flag = False
		for i in range(n):
			(arr[i][swap_pos[0]], arr[i][swap_pos[1]]) = (arr[i][swap_pos[1]], arr[i][swap_pos[0]])
			for j in range(m - 1):
				if arr[i][j] > arr[i][j + 1]:
					flag = True
					print(-1)
					break
			if flag:
				break
		if not flag:
			print(f'{swap_pos[0] + 1} {swap_pos[1] + 1}')


import math
for _ in range(int(input())):
	(row, column) = map(int, input().split())
	matrix = []
	for i in range(row):
		matrix.append(list(map(int, input().split())))
	x = True
	y = [1, 1]
	j = 0
	asd = True
	while x is True and j < row:
		a = matrix[j]
		b = sorted(a)
		t = []
		for i in range(column):
			if a[i] != b[i]:
				t.append(i)
		if len(t) > 2:
			x = False
			y = [-1]
			asd = False
		elif len(t) == 2:
			(s1, s2) = t
			y = [s1 + 1, s2 + 1]
			x = False
		else:
			j += 1
			continue
	if x is True or asd is False:
		print(*y)
	else:
		zz = 0
		while zz < row:
			a = matrix[zz]
			(a[s1], a[s2]) = (a[s2], a[s1])
			b = sorted(a)
			for i in range(column):
				if a[i] != b[i]:
					y = [-1]
					zz = row + 1
					break
			zz += 1
		print(*y)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		l = list(map(int, input().strip().split()))
		a.append(l)
	idx = []
	for i in range(n):
		b = a[i]
		d = sorted(b)
		for j in range(m):
			if b[j] != d[j]:
				idx.append(j)
		if len(idx) > 0:
			break
	if len(idx) == 0:
		print(1, 1)
	elif len(idx) == 2:
		for i in range(n):
			(a[i][idx[0]], a[i][idx[1]]) = (a[i][idx[1]], a[i][idx[0]])
		f = 0
		for i in range(n):
			b1 = a[i]
			d1 = sorted(b1)
			if b1 != d1:
				f = 1
				break
		if f == 0:
			print(idx[0] + 1, idx[1] + 1)
		else:
			print(-1)
	else:
		print(-1)


t = int(input())
while t:
	(n, m) = map(int, input().split())
	a = list()
	for i in range(n):
		a.append(list(map(int, input().split())))
	x = list()
	i = 0
	while i < n and (not len(x)):
		k = list(a[i])
		k.sort()
		for j in range(m):
			if a[i][j] != k[j]:
				x.append(j)
		i += 1
	if not len(x):
		print('1 1')
		t -= 1
		continue
	elif len(x) != 2:
		print(-1)
		t -= 1
		continue
	for i in a:
		(i[x[0]], i[x[1]]) = (i[x[1]], i[x[0]])
	ok = True
	for i in a:
		j = 0
		while j < m - 1:
			if i[j] > i[j + 1]:
				ok = False
				break
			j += 1
		if not ok:
			break
	if ok:
		print(x[0] + 1, x[1] + 1)
	else:
		print(-1)
	t -= 1


def solve(arr):
	n = len(arr)
	m = len(arr[0])
	sorted_arr = []
	for row in arr:
		sorted_arr.append(sorted(row))
	badIdx = []
	for i in range(n):
		for j in range(m):
			if arr[i][j] != sorted_arr[i][j]:
				badIdx.append(j)
		if len(badIdx) >= 2:
			break
	if len(badIdx) == 0:
		print(1, 1)
		return
	if len(badIdx) != 2:
		print(-1)
		return
	for i in range(n):
		(arr[i][badIdx[0]], arr[i][badIdx[1]]) = (arr[i][badIdx[1]], arr[i][badIdx[0]])
	for i in range(n):
		for j in range(m):
			if arr[i][j] != sorted_arr[i][j]:
				print(-1)
				return
	print(badIdx[0] + 1, badIdx[1] + 1)

def get_input():
	matrix_size = input()
	n = int(matrix_size.split()[0])
	m = int(matrix_size.split()[1])
	arr = []
	for i in range(n):
		row = input()
		arr.append(list(map(int, row.split())))
	return arr
t = int(input())
for i in range(t):
	arr = get_input()
	solve(arr)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	rows = [list(map(int, input().split())) for i in range(n)]
	guess = None
	for r in range(n):
		row = rows[r]
		fixed = sorted(row)
		indexes = [i for i in range(m) if fixed[i] != row[i]]
		if len(indexes) > 2:
			break
		if len(indexes) == 2:
			if guess is None:
				guess = indexes
			elif guess != indexes:
				break
	else:
		if guess is None:
			print('1 1')
			continue
		else:
			for r in range(n):
				row = rows[r]
				if row[guess[0]] < row[guess[1]]:
					break
			else:
				print(guess[0] + 1, guess[1] + 1)
				continue
	print(-1)


def ss(g, m, n):
	l = [[0, 0] for _ in range(m)]
	for i in range(m):
		t = sorted(g[i])
		c = 0
		for j in range(n):
			if t[j] != g[i][j]:
				if c == 2:
					return -1
				elif c == 0:
					c += 1
					l[i][0] = j
				else:
					c += 1
					l[i][1] = j
	t = [0, 0]
	for i in l:
		if i != [0, 0]:
			t = i
			break
	if t == [0, 0]:
		return t
	for i in range(m):
		(g[i][t[0]], g[i][t[1]]) = (g[i][t[1]], g[i][t[0]])
		for j in range(1, n):
			if g[i][j] < g[i][j - 1]:
				return -1
	return t
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	g = []
	for i in range(m):
		g.append(list(map(int, input().split())))
	ans = ss(g, m, n)
	if ans == -1:
		print(-1)
	else:
		print(ans[0] + 1, ans[1] + 1)


import math, sys
input = sys.stdin.readline
inf = 1e+18
mod = 10 ** 9 + 7
pi = math.pi
e = math.e
modinv = lambda x, m: pow(x, m - 2, m)
import bisect
import heapq
mod9 = 998244353
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	pos = True
	inv = []
	a = []
	for p in range(n):
		arr = list(map(int, input().split()))
		sor = sorted(arr)
		my = []
		for i in range(m):
			if arr[i] != sor[i]:
				my.append(i + 1)
		if len(my) > 2:
			pos = False
		elif len(my) == 0:
			my = [1, 1]
		a.append(arr)
		inv.append(my)
	if not pos:
		print(-1)
		continue
	v = [1, 1]
	for i in inv:
		if i != [1, 1]:
			if v != [1, 1] and v != i:
				pos = False
				break
			v = i
	if not pos:
		print(-1)
		continue
	elif v == [1, 1]:
		print(*v)
		continue
	for i in range(n):
		if a[i][v[0] - 1] < a[i][v[1] - 1]:
			pos = False
			break
	if not pos:
		print(-1)
	else:
		print(*v)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	for _ in range(n):
		a.append(list(map(int, input().split())))
	sorteda = []
	for i in a:
		sorteda.append(sorted(i))
	unsortindex = set()
	ls = []
	for i in range(n):
		l = 0
		for j in range(m):
			if a[i][j] != sorteda[i][j]:
				unsortindex.add(j)
				l += 1
		ls.append(l)
	unsortindex = list(unsortindex)
	if len(unsortindex) == 0:
		print(1, 1)
		continue
	elif len(unsortindex) > 2:
		print(-1)
		continue
	else:
		f = 0
		for i in range(n):
			if ls[i] != 2 and a[i][unsortindex[0]] != a[i][unsortindex[1]]:
				print(-1)
				f = -1
				break
		if f == 0:
			print(unsortindex[0] + 1, unsortindex[1] + 1)


R = lambda : [*map(int, input().split())]
for _ in [0] * R()[0]:
	(n, m) = R()
	a = [R() for _ in [0] * n]
	(*b,) = map(sorted, a)
	i = j = 0
	for (r, q) in zip(a, b):
		if (c := [i for (i, x, y) in zip(range(m), r, q) if x != y]):
			(i, j) = c[:2]
	if i < j:
		for r in a:
			(r[i], r[j]) = (r[j], r[i])
	print(*((i + 1, j + 1), [-1])[a > b])


def is_sorted(l):
	return all((l[i] <= l[i + 1] for i in range(len(l) - 1)))
t = int(input())
for c in range(t):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	mat = []
	for i in range(n):
		mat.append([int(x) for x in input().split()])
	(first, last) = (0, 0)
	for k in range(n):
		for i in range(m - 1):
			if mat[k][i] > mat[k][i + 1]:
				first = i
				while first > 0 and mat[k][first] == mat[k][first - 1]:
					first -= 1
				break
		for i in range(m - 1, 0, -1):
			if mat[k][i] < mat[k][i - 1]:
				last = i
				while last < m - 1 and mat[k][last] == mat[k][last + 1]:
					last += 1
				break
		if first != last:
			break
	fail = False
	for i in range(n):
		(mat[i][first], mat[i][last]) = (mat[i][last], mat[i][first])
		if not is_sorted(mat[i]):
			fail = True
			break
	print(-1 if fail else '%d %d' % (first + 1, last + 1))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	matrix = []
	for _ in range(n):
		matrix.append(list(map(int, input().split())))
	sorted_matrix = []
	for row in matrix:
		sorted_matrix.append(sorted(row))
	total_incorrect = 0
	wrongs = []
	for i in range(n):
		for j in range(m):
			if matrix[i][j] != sorted_matrix[i][j]:
				wrongs.append(j)
	wrongs = list(set(wrongs))
	if len(wrongs) > 2:
		print(-1)
		continue
	if wrongs == []:
		print(1, 1)
	else:
		can = True
		for (i, item) in enumerate(matrix):
			(item[wrongs[0]], item[wrongs[1]]) = (item[wrongs[1]], item[wrongs[0]])
		for (i, item) in enumerate(matrix):
			if item != sorted(item):
				can = False
		if can:
			print(wrongs[0] + 1, wrongs[1] + 1)
		else:
			print(-1)


t = int(input())
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	a = []
	b = []
	swap = [0] * m
	for i in range(n):
		a += [list(map(int, input().split()))]
		b += [sorted(a[i])]
	idx = -1
	jdx = -1
	k = 0
	for i in range(n):
		for j in range(m):
			if a[i][j] != b[i][j]:
				if swap[j] != 1:
					k += 1
					swap[j] = 1
	if k == 0:
		print(1, 1)
	elif k == 2:
		idx = 0
		while swap[idx] != 1:
			idx += 1
		jdx = m - 1
		while swap[jdx] != 1:
			jdx -= 1
		ans = 0
		for i in range(n):
			if a[i][idx] != b[i][jdx]:
				ans = -1
		if ans == -1:
			print(ans)
		else:
			print(*sorted([idx + 1, jdx + 1]))
	else:
		print(-1)


for inh in range(int(input())):
	(n, m) = map(int, input().split())
	(a, hehe) = ([], [])
	for i in range(n):
		k = list(map(int, input().split()))
		a.append(k)
		b = k.copy()
		b.sort()
		hehe.append(b)
	for i in range(n):
		k = 0
		(x, y) = (-1, -1)
		for j in range(m):
			if a[i][j] != hehe[i][j]:
				k += 1
				if x == -1:
					x = j
				else:
					y = j
		if k > 0:
			break
	if x == -1:
		print(1, 1)
	elif k > 2:
		print(-1)
	else:
		for i in range(n):
			(a[i][x], a[i][y]) = (a[i][y], a[i][x])
		ans = True
		for i in range(n):
			for j in range(m):
				if a[i][j] != hehe[i][j]:
					ans = False
					break
			if not ans:
				break
		if ans:
			print(x + 1, y + 1)
		else:
			print(-1)


def sortcheck(ar):
	for i in range(0, len(ar) - 1):
		if ar[i] > ar[i + 1]:
			return False
	return True
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for _ in range(n):
		tl = list(map(int, input().split()))
		l.append(tl)
	(u, v, issorted) = (-1, -1, 1)
	possible = 1
	for i in range(0, n):
		tl = list(l[i])
		tl.sort()
		inv = []
		for p in range(0, m):
			if tl[p] != l[i][p]:
				inv.append(p)
		if len(inv) == 0:
			continue
		issorted = 0
		if len(inv) > 2:
			possible = 0
			break
		(u, v) = (inv[0], inv[1])
		for k in range(0, n):
			(l[k][u], l[k][v]) = (l[k][v], l[k][u])
		break
	fin = possible
	for x in l:
		fin &= sortcheck(x)
	if issorted:
		print(1, 1)
	elif fin:
		print(u + 1, v + 1)
	else:
		print(-1)


R = lambda : [*map(int, input().split())]
(t,) = R()
for _ in range(t):
	(n, m) = R()
	a = [R() for _ in [0] * n]
	(*b,) = map(sorted, a)
	i = j = 0
	for (r1, r2) in zip(a, b):
		d = [i for (i, x, y) in zip(range(m), r1, r2) if x != y]
		if d:
			(i, j) = d[:2]
			break
	for r in a:
		(r[i], r[j]) = (r[j], r[i])
	print(*((i + 1, j + 1), [-1])[a > b])


t = int(input())
result = []
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	a = []
	b = []
	for i in range(n):
		col1 = list(map(int, input().split()))
		col2 = col1.copy()
		col2.sort()
		a.append(col1)
		b.append(col2)
	s = set()
	for i in range(n):
		for j in range(m):
			if a[i][j] != b[i][j]:
				s.add(j)
	if len(s) > 2:
		print(-1)
	elif len(s) == 0:
		print(1, 1)
	else:
		x = 0
		y = 0
		for e in s:
			x = e
			s.remove(e)
			break
		for e in s:
			y = e
			s.remove(e)
			break
		for i in range(n):
			temp = a[i][y]
			a[i][y] = a[i][x]
			a[i][x] = temp
		flag = True
		for i in range(n):
			for j in range(m):
				if a[i][j] != b[i][j]:
					flag = False
		if flag:
			print(x + 1, y + 1)
		else:
			print(-1)


R = lambda : [*map(int, input().split())]
for _ in [0] * R()[0]:
	(n, m) = R()
	a = [R() for _ in [0] * n]
	(*b,) = map(sorted, a)
	i = j = 0
	for t in zip(a, b):
		(i, j, *_) = [i for (i, x, y) in zip(range(m), *t) if x ^ y] or (i, j)
	for r in a:
		(r[i], r[j]) = (r[j], r[i])
	print(*((i + 1, j + 1), [-1])[a > b])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		s = list(map(int, input().split()))
		a.append(s)
	res = []
	for i in a:
		res.append(sorted(i))
	(x, y) = (-1, -1)
	ok = True
	for i in range(n):
		for j in range(m):
			if res[i][j] != a[i][j]:
				if x == -1:
					x = j
				elif y == -1:
					y = j
				if x >= 0 and y >= 0:
					break
		if x >= 0 and y >= 0:
			break
	for i in range(n):
		for j in range(m):
			if j == y and res[i][j] == a[i][j] and (a[i][x] != a[i][y]):
				ok = False
			if a[i][j] != res[i][j] and j not in [x, y]:
				ok = False
	if not ok:
		print(-1)
	elif [x, y] == [-1, -1]:
		print(1, 1)
	else:
		print(x + 1, 1 + y)


for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = [0] * n
	b = [0] * n
	x = 0
	y = 0
	count = 0
	for i in range(n):
		a[i] = list(map(int, input().split()))
		b[i] = a[i]
		b[i] = sorted(b[i])
	for i in range(n):
		for j in range(m):
			if a[i][j] != b[i][j]:
				count += 1
				if count == 1:
					x = j
				elif count == 2:
					y = j
		if count >= 2:
			break
	if count == 0:
		print(1, 1)
	else:
		for i in range(n):
			temp = a[i][x]
			a[i][x] = a[i][y]
			a[i][y] = temp
		if a == b:
			print(x + 1, y + 1)
		else:
			print(-1)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	arr_sorted = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
		arr_sorted.append(sorted(arr[i]))
	for i in range(n):
		ind = 0
		cnt = 0
		flag = 0
		for j in range(m):
			if arr[i][j] != arr_sorted[i][j]:
				if cnt == 0:
					start = j
				else:
					end = j
				cnt += 1
			if cnt == 2:
				flag = 1
				break
		if flag != 0:
			break
	if flag == 0:
		print(1, 1)
	else:
		for i in range(n):
			(arr[i][start], arr[i][end]) = (arr[i][end], arr[i][start])
		for i in range(n):
			for j in range(m):
				if arr[i][j] != arr_sorted[i][j]:
					flag = 2
					break
			if flag != 1:
				break
		if flag == 1:
			print(start + 1, end + 1)
		else:
			print(-1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mat = []
	arr = []
	for i in range(n):
		temp = [int(x) for x in input().split()]
		mat.append(temp)
		arr.append(sorted(temp))
	diff = []
	same = True
	for i in range(n):
		count = 0
		cols = []
		for j in range(m):
			if mat[i][j] != arr[i][j]:
				count += 1
				cols.append(j)
		if count > 2:
			same = False
			break
		elif cols:
			diff.append(tuple(cols))
	if same:
		st = set(diff)
		if len(st) == 0:
			print(1, 1)
		elif len(st) == 1:
			(a, b) = (diff[0][0], diff[0][1])
			hehe = False
			for i in range(n):
				if mat[i][b] > mat[i][a]:
					hehe = True
					break
			if hehe:
				print(-1)
			else:
				print(a + 1, b + 1)
		else:
			print(-1)
	else:
		print(-1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(L, R) = (0, 0)
	b = 0
	ll = []
	for i in range(n):
		l = list(map(int, input().split()))
		ll.append(l.copy())
		if b:
			continue
		sl = sorted(l)
		(l[L], l[R]) = (l[R], l[L])
		for j in range(m):
			if l[j] != sl[j]:
				if L != R:
					b = 1
				R = m - l[::-1].index(sl[j]) - 1
				L = j
				(l[L], l[R]) = (l[R], l[L])
	for i in range(n):
		l = ll[i]
		if b:
			continue
		sl = sorted(l)
		(l[L], l[R]) = (l[R], l[L])
		for j in range(m):
			if l[j] != sl[j]:
				if L != R:
					b = 1
	if b:
		print(-1)
	else:
		print(L + 1, R + 1)