AtCoder Beginner Contest 139 - League

N players will participate in a tennis tournament. We will call them Player 1, Player 2, \ldots, Player N.
The tournament is round-robin format, and there will be N(N-1)/2 matches in total.
Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.
 - Each player plays at most one matches in a day.
 - Each player i (1 \leq i \leq N) plays one match against Player A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} in this order.

-----Constraints-----
 - 3 \leq N \leq 1000
 - 1 \leq A_{i, j} \leq N
 - A_{i, j} \neq i
 - A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} are all different.

-----Input-----
Input is given from Standard Input in the following format:
N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}

-----Output-----
If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1.

-----Sample Input-----
3
2 3
1 3
1 2

-----Sample Output-----
3

All the conditions can be satisfied if the matches are scheduled for three days as follows:
 - Day 1: Player 1 vs Player 2
 - Day 2: Player 1 vs Player 3
 - Day 3: Player 2 vs Player 3
This is the minimum number of days required.

Source: atcoder | Difficulty: MEDIUM


Solutions:
from collections import deque
n = int(input())
l = [[int(i) - 1 for i in input().split()] for i in range(n)]
q = deque(list(range(n)))
days = [0 for i in range(n)]
pairs = [-1 for i in range(n)]
while q:
	a = q.popleft()
	if len(l[a]) == 0:
		continue
	b = l[a].pop(0)
	if pairs[b] == a:
		days[a] = days[b] = max(days[a], days[b]) + 1
		q.append(a)
		q.append(b)
	else:
		pairs[a] = b
print(max(days) if not any(l) else -1)


from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
A = []
for _ in range(N):
	line = list([int(x) - 1 for x in input().split()])
	A.append(line)
cnt = [0] * N
recent = [0] * N
Q = deque(list(range(N)))
while Q:
	p1 = Q.popleft()
	if cnt[p1] < N - 1:
		p2 = A[p1][cnt[p1]]
		if cnt[p2] < N - 1:
			if A[p2][cnt[p2]] == p1:
				day = max(recent[p1], recent[p2]) + 1
				recent[p1] = day
				recent[p2] = day
				cnt[p1] += 1
				cnt[p2] += 1
				Q.append(p1)
				Q.append(p2)
if min(cnt) != N - 1:
	print(-1)
else:
	print(max(recent))


import time
start = time.time()
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
s = [0 for i in range(n)]
ans = 0
need = n * (n - 1) // 2
while need:
	c = [0 for i in range(n)]
	ans += 1
	for first in range(n):
		if c[first] == 0 and s[first] < n - 1:
			second = a[first][s[first]] - 1
			second_num = s[second]
			if c[second] == 0 and a[second][second_num] - 1 == first:
				c[first] = 1
				c[second] = 1
				s[first] += 1
				s[second] += 1
				need -= 1
	if sum(c) == 0:
		print(-1)
		exit()
	now = time.time() - start
	if now > 1.835:
		print(n * (n - 1) // 2)
		exit()
print(ans)


n = int(input())
a = []
for _ in range(n):
	a.append(list(map(lambda x: int(x) - 1, input().split())))
cnt = [0 for _ in range(n)]
now = []
for i in range(n):
	j = a[i][cnt[i]]
	if a[j][cnt[j]] == i and i < j:
		now.append([i, j])
ans = 0
while now:
	last = now
	now = []
	for x in last:
		i = x[0]
		j = x[1]
		cnt[i] += 1
		cnt[j] += 1
		if cnt[i] < n - 1:
			k = a[i][cnt[i]]
			if a[k][cnt[k]] == i:
				now.append([i, k])
		if cnt[j] < n - 1:
			k = a[j][cnt[j]]
			if a[k][cnt[k]] == j:
				now.append([j, k])
	ans += 1
if all((cnt[i] == n - 1 for i in range(n))):
	print(ans)
else:
	print(-1)


import sys
input = sys.stdin.readline

def main():
	N = int(input())
	Id = {}
	cur = 0
	for i in range(1, N + 1):
		for j in range(i + 1, N + 1):
			Id[i, j] = cur
			cur += 1
	G = [[] for i in range(N * (N - 1) // 2)]
	size = [0] * (N * (N - 1) // 2)
	for i in range(1, N + 1):
		for (idx, j) in enumerate(list(map(int, input().split()))):
			if i < j:
				k = Id[i, j]
			else:
				k = Id[j, i]
			if idx:
				G[par].append(k)
				size[k] += 1
			par = k
	g = [idx for (idx, s) in enumerate(size) if s == 0]
	ans = 0
	while g:
		ans += 1
		n_g = []
		for v in g:
			length = len(G[v])
			if not length:
				continue
			size[G[v][0]] -= 1
			if not size[G[v][0]]:
				n_g.append(G[v][0])
			if length == 2:
				size[G[v][1]] -= 1
				if not size[G[v][1]]:
					n_g.append(G[v][1])
		g = n_g
	for s in size:
		if s != 0:
			print(-1)
			return
	print(ans)

def __starting_point():
	main()
__starting_point()


def main():
	N = int(input())
	A = []
	for _ in range(N):
		a = list(map(int, input().split()))
		a = [i - 1 for i in a]
		a.reverse()
		A.append(a)
	t = N * (N - 1) / 2
	d = 0
	n = set(range(N))
	while True:
		p = 0
		l = set()
		d += 1
		for i in n:
			if A[i] == [] or i in l:
				continue
			j = A[i][-1]
			if A[i][-1] not in l and A[j][-1] == i:
				l.add(i)
				l.add(A[i][-1])
				A[j].pop()
				A[i].pop()
				t -= 1
				p += 1
		n = l
		if t == 0:
			print(d)
			break
		if p == 0:
			print(-1)
			break
main()


from sys import setrecursionlimit

def encode(i, j):
	if i < j:
		(i, j) = (j, i)
	return i * (i - 1) // 2 + j + 1

def dfs(v):
	if visited[v] == 2:
		return dp[v]
	visited[v] = 1
	for nv in g[v]:
		if visited[nv] == 1:
			print(-1)
			exit()
		dp[v] = max(dp[v], dfs(nv) + 1)
	visited[v] = 2
	return dp[v]
setrecursionlimit(10 ** 6)
N = int(input())
GAMES_CNT = N * (N - 1) // 2
g = [[] for _ in range(GAMES_CNT + 1)]
for i in range(N):
	orig = 0
	for j in map(lambda x: int(x) - 1, input().split()):
		dest = encode(i, j)
		g[orig].append(dest)
		orig = dest
dp = [0] * (GAMES_CNT + 1)
visited = [0] * (GAMES_CNT + 1)
print(dfs(0))


from collections import deque
n = int(input())
a = [list([int(x) - 1 for x in input().split()]) + [-1] for _ in range(n)]
(l, day) = ([0] * n, [0] * n)
que = deque([i for i in range(n)])
while que:
	u = que.popleft()
	v = a[u][l[u]]
	if a[v][l[v]] == u:
		day[u] = max(day[u], day[v]) + 1
		day[v] = day[u]
		l[u] += 1
		l[v] += 1
		que.append(u)
		que.append(v)
if any((x != n - 1 for x in l)):
	print(-1)
	return
print(max(day))


n = int(input())
g = [[] for _ in range(n ** 2)]
inv = [0] * n ** 2
for i in range(n):
	a = list(map(lambda x: int(x) - 1, input().split()))
	for j in range(n - 2):
		(p, q) = (min(i, a[j]), max(i, a[j]))
		(r, s) = (min(i, a[j + 1]), max(i, a[j + 1]))
		g[p * n + q].append(r * n + s)
		inv[r * n + s] += 1
s = []
for i in range(n):
	for j in range(i + 1, n):
		if inv[i * n + j] == 0:
			s.append(i * n + j)
d = [0] * n ** 2
while s:
	p = s.pop()
	for node in g[p]:
		d[node] = max(d[node], d[p] + 1)
		inv[node] -= 1
		if inv[node] == 0:
			s.append(node)
for i in range(n):
	for j in range(i + 1, n):
		if inv[i * n + j] > 0:
			print(-1)
			exit(0)
print(max(d) + 1)


from collections import deque
n = int(input())
a = [0] * n
for i in range(n):
	a[i] = list(map(lambda x: int(x) - 1, input().split()))
	a[i].append(-1)
t = [a[i][0] for i in range(n)]
l = [0] * n
day = [0] * n
q = deque([i for i in range(n)])
while q:
	u = q.popleft()
	v = a[u][l[u]]
	if a[v][l[v]] == u:
		day[u] = day[v] = max(day[u], day[v]) + 1
		l[u] += 1
		l[v] += 1
		q.append(u)
		q.append(v)
if any((x != n - 1 for x in l)):
	print(-1)
	exit()
print(max(day))


from collections import deque
n = int(input())
a = [0] + list((deque(map(int, input().split())) for _ in range(n)))
(cnt, cur, days) = (0, [0] * (n + 1), [0] * (n + 1))
q = deque(list(range(1, n + 1)))
while q:
	x = q.popleft()
	if not a[x]:
		continue
	y = a[x].popleft()
	if cur[y] == x:
		cnt += 1
		days[x] = days[y] = max(days[x], days[y]) + 1
		(cur[x], cur[y]) = (0, 0)
		q.append(x)
		q.append(y)
	else:
		cur[x] = y
res = max(days) if cnt == n * (n - 1) // 2 else -1
print(res)


N = int(input())
A = [[x - 1 for x in list(map(int, input().split()))[::-1]] for _ in range(N)]

def can_match(i, A, next_set):
	if not A[i]:
		return
	j = A[i][-1]
	if A[j][-1] == i:
		if i < j:
			next_set.add((i, j))
		else:
			next_set.add((j, i))
next_set = set()
for i in range(N):
	can_match(i, A, next_set)
day = 0
battle = 0
while next_set:
	day += 1
	(current_set, next_set) = (next_set.copy(), set())
	for match in current_set:
		battle += 1
		del A[match[0]][-1]
		can_match(match[0], A, next_set)
		del A[match[1]][-1]
		can_match(match[1], A, next_set)
if battle == N * (N - 1) // 2:
	print(day)
else:
	print(-1)


import sys
n = int(input())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
maxmatch = n * (n - 1)
day = 0
q = [i for i in range(n)]
nq = []
match = [0] * (n + 1)
check = [0] * (n + 1)
while q:
	day += 1
	for i in q:
		if match[i] == n - 1 or check[i] == day:
			continue
		else:
			vs = a[i][match[i]] - 1
			if check[vs] != day and a[vs][match[vs]] - 1 == i:
				match[i] += 1
				match[vs] += 1
				match[n] += 2
				check[i] = day
				check[vs] = day
				check[n] = day
				nq.append(i)
				nq.append(vs)
		if i == q[-1]:
			if check[n] != day:
				print(-1)
				sys.exit()
	if match[n] == maxmatch:
		break
	q = nq[:]
	nq = []
print(day)


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
calc = lambda u, v: min(u, v) * n + max(u, v)
edge = [[] for _ in range(n * n)]
for i in range(n):
	for j in range(1, n - 1):
		(u, v) = (calc(a[i][j - 1] - 1, i), calc(a[i][j] - 1, i))
		edge[u].append(v)
from collections import deque

def find_loop(n, e):
	x = [0] * n
	d = deque()
	t = []
	c = 0
	for i in range(n):
		for j in e[i]:
			x[j] += 1
	for i in range(n):
		if x[i] == 0:
			d.append(i)
			t.append(i)
			c += 1
	while d:
		i = d.popleft()
		for j in e[i]:
			x[j] -= 1
			if x[j] == 0:
				d.append(j)
				t.append(j)
				c += 1
	return t
d = find_loop(n * n, edge)
if len(d) != n * n:
	exit(print(-1))
c = [1] * n * n
for i in d:
	for j in edge[i]:
		c[j] = c[i] + 1
print(max(c))


from sys import stdin
N = int(stdin.readline().rstrip())
A = [0] * N
l = [[int(x) for x in stdin.readline().rstrip().split()] for _ in A]
d = 1
k = N * (N - 1)
while sum(A) < k and d < 10 ** 4:
	L = [1] * N
	y = 0
	d += 1
	for i in range(N):
		if A[i] < N - 1:
			x = l[i][A[i]] - 1
			if l[x][A[x]] * L[x] * L[i] == i + 1:
				A[i] += 1
				A[x] += 1
				L[i] = L[x] = 0
				y = 1
print([k // 2, d * y - 1][d * y < 9999])


from collections import deque
N = int(input())
A = [deque() for _ in range(N)]
for i in range(N):
	for aa in list(map(int, input().split())):
		aa -= 1
		A[i].append(aa)

def check(i):
	if len(A[i]) == 0:
		return
	j = A[i][0]
	if len(A[j]) == 0:
		return
	if A[j][0] == i:
		if j < i:
			(i, j) = (j, i)
		q.add((i, j))
q = set()
for i in range(N):
	check(i)
ans = 0
while q:
	ans += 1
	prevq = q
	q = set()
	for p in prevq:
		(i, j) = p
		A[i].popleft()
		A[j].popleft()
	for p in prevq:
		(i, j) = p
		check(i)
		check(j)
for i in range(N):
	if len(A[i]) != 0:
		print(-1)
		exit()
print(ans)


from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
A = [0] + [list(map(lambda x: tuple(sorted((i, int(x)))), input().split())) for i in range(1, N + 1)]
Idx = [0] * (N + 1)
pool = set()
q = deque([a[0] for a in A[1:]])
ans = 1
s = set()
while q:
	p = q.popleft()
	if p in pool:
		pool.remove(p)
		(a, b) = p
		Idx[a] += 1
		Idx[b] += 1
		if a in s or b in s:
			ans += 1
			s = {a, b}
		else:
			s.add(a)
			s.add(b)
		if Idx[a] < N - 1:
			q.append(A[a][Idx[a]])
		if Idx[b] < N - 1:
			q.append(A[b][Idx[b]])
	else:
		pool.add(p)
if pool:
	print(-1)
else:
	print(ans)


import sys
from collections import deque
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
N = ir()
A = [deque(lr()) for _ in range(N)]
candidate = list(range(N))
match = 0
day = 0
while True:
	day += 1
	used = set()
	next = set()
	bool = False
	for c in candidate:
		if len(A[c]) == 0:
			continue
		op = A[c][0] - 1
		if c in used or op in used:
			continue
		if A[op][0] - 1 == c:
			bool = True
			A[c].popleft()
			A[op].popleft()
			match += 1
			next |= {c, op}
			used |= {c, op}
	if match == N * (N - 1) // 2:
		break
	if not bool:
		print(-1)
		return
	candidate = next
print(day)


import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

def main():
	n = int(input())
	A = [list(map(int, input().split()))[::-1] for i in range(n)]
	day = 0
	zan = [n - 1] * n
	zann = sum(zan)
	sumi = set(range(n))
	while True:
		day += 1
		kouho = list(sumi)
		sumi = set()
		for i in kouho:
			try:
				if A[A[i][-1] - 1][-1] - 1 == i:
					sumi.add(i)
					sumi.add(A[i][-1] - 1)
			except:
				pass
		for k in sumi:
			A[k].pop()
			zan[k] -= 1
		if zann == sum(zan):
			print(-1)
			exit(0)
		zann = sum(zan)
		if zann == 0:
			print(day)
			exit(0)
main()


from collections import deque

def main():
	n = int(input())
	a = [0] * n
	for i in range(n):
		a[i] = deque(list(map(lambda x: int(x) - 1, input().split())))
	tmp = set()
	for (p1, p) in enumerate(a):
		p2 = p[0]
		if p1 == a[p2][0]:
			tmp.add(p1)
			tmp.add(p2)
	q = deque(tmp)
	for i in tmp:
		a[i].popleft()
	day = 0
	while True:
		day += 1
		tmp = set()
		while q:
			p1 = q.popleft()
			if len(a[p1]) == 0:
				continue
			p2 = a[p1][0]
			if p1 == a[p2][0]:
				tmp.add(p1)
				tmp.add(p2)
		q = deque(tmp)
		for i in tmp:
			a[i].popleft()
		tmp = set()
		if len(q) == 0:
			break
	for i in a:
		if i:
			print(-1)
			exit()
	print(day)
main()


import sys
import collections
import copy
input = sys.stdin.readline

def main():
	N = int(input())
	A = [collections.deque([int(x) for x in input().split()]) for _ in range(N)]
	day = 0
	c = 0
	nxt = [x for x in range(N)]
	oppo = [0] * N
	while c != N * (N - 1):
		day += 1
		for i in nxt:
			oppo[i] = A[i].popleft() if A[i] else -1
		tmp = set()
		for i in nxt:
			if i == -1 or i in tmp:
				continue
			if i == oppo[oppo[i] - 1] - 1:
				tmp.add(i)
				tmp.add(oppo[i] - 1)
				c += 2
		if not tmp:
			print(-1)
			return
		nxt = tmp
	print(day)
main()


n = int(input())
raw = []
for _ in range(n):
	raw.append(list(map(lambda x: int(x) - 1, input().split())))
cnt = [0 for _ in range(n)]
now = []
for i in range(n):
	j = raw[i][cnt[i]]
	if i < j and i == raw[j][cnt[j]]:
		now.append(i)
		now.append(j)
ans = 0
while now:
	ans += 1
	last = now
	now = []
	for x in last:
		cnt[x] += 1
		if cnt[x] < n - 1:
			y = raw[x][cnt[x]]
			if x == raw[y][cnt[y]]:
				now.append(x)
				now.append(y)
if cnt == [n - 1 for _ in range(n)]:
	print(ans)
else:
	print(-1)


from collections import Counter
N = int(input())
Ass = [list(map(int, input().split())) for _ in range(N)]
ct = Counter()
q = set([(i, 0) for i in range(N)])
idxs = [0] * N
n = 0
ans = 0
while q:
	nq = set()
	for (i, k) in q:
		a = i + 1
		b = Ass[i][k]
		if a > b:
			(a, b) = (b, a)
		ct[a, b] += 1
		if ct[a, b] == 2:
			n += 1
			idxs[a - 1] += 1
			if idxs[a - 1] < N - 1:
				nq.add((a - 1, idxs[a - 1]))
			idxs[b - 1] += 1
			if idxs[b - 1] < N - 1:
				nq.add((b - 1, idxs[b - 1]))
	ans += 1
	q = nq
if n == N * (N - 1) // 2:
	print(ans)
else:
	print(-1)


n = int(input())
lst = [list(map(int, input().split())) for _ in range(n)]
current = []
for i in range(n):
	current.append(lst[i].pop(0))
count = 0
players = set(range(1, n + 1))
while True:
	index_lst = []
	for i in players:
		candidate = current[i - 1]
		if candidate in index_lst:
			continue
		if current[candidate - 1] == i:
			index_lst += [i, candidate]
	if len(index_lst) == 0:
		if sum(current) == 0:
			print(count)
			break
		else:
			print(-1)
			break
	for i in index_lst:
		if len(lst[i - 1]) == 0:
			current[i - 1] = 0
		else:
			current[i - 1] = lst[i - 1].pop(0)
	players = set(index_lst)
	count += 1


n = int(input())
l = [list(map(int, input().split())) for i in [0] * n]
a = [0] * n
d = 1
k = n * (n - 1)
while sum(a) < k and d < 9999:
	L = [0] * n
	y = 0
	d += 1
	for i in range(n):
		if a[i] < n - 1:
			x = l[i][a[i]] - 1
			if l[x][a[x]] - 1 == i and L[x] + L[i] < 1:
				a[i] += 1
				a[x] += 1
				L[i] = L[x] = y = 1
print([k // 2, d * y - 1][d * y < 9999])


N = int(input())
a = [[0 for j in range(N - 1)] for i in range(N)]
for i in range(N):
	line = list(map(int, input().split()))
	for j in range(N - 1):
		a[i][j] = line[j] - 1
	a[i] = a[i][::-1]
stack = []

def addmatch(i):
	if len(a[i]) == 0:
		return
	j = a[i][-1]
	if a[j][-1] == i:
		stack.append([i, j])
for i in range(N):
	addmatch(i)
day = 0
while stack:
	day += 1
	member = set()
	for i in range(len(stack)):
		g = stack.pop()
		y = g[0]
		x = g[1]
		if len(a[y]) > 0 and a[y][-1] == x:
			a[y].pop()
			a[x].pop()
			member.add(y)
			member.add(x)
	for m in member:
		addmatch(m)
for i in range(len(a)):
	if len(a[i]) > 0:
		print(-1)
		break
else:
	print(day)


from collections import deque
n = int(input())
matches = []
for _ in range(n):
	matches.append(list([int(x) - 1 for x in input().split()]))
q = deque(list(range(n)))
days = [0] * n
while q:
	x = q.popleft()
	if len(matches[x]) == 0:
		continue
	y = matches[x][0]
	if matches[y][0] == x:
		day = max(days[x], days[y]) + 1
		days[x] = day
		days[y] = day
		q.append(x)
		q.append(y)
		_ = matches[x].pop(0)
		_ = matches[y].pop(0)
if not any(matches):
	print(max(days))
else:
	print(-1)


from collections import deque
n = int(input())
m = []
for i in range(n):
	a = [*map(int, input().split())]
	m.append(a)
d = [0] * n
c = [0] * n
q = deque(range(n))
while q:
	p = q.popleft()
	if c[p - 1] < n - 1:
		e = m[p - 1][c[p - 1]]
		if p == m[e - 1][c[e - 1]]:
			t = max(d[p - 1], d[e - 1]) + 1
			d[p - 1] = t
			d[e - 1] = t
			c[p - 1] += 1
			c[e - 1] += 1
			q.append(p)
			q.append(e)
if min(c) != n - 1:
	print(-1)
else:
	print(max(d))


import sys
n = int(input())
l = [list(map(int, input().split())) for i in range(n)]
ct = [0 for i in range(n)]
fin = 0
day = 0
count = 0
check = [0, 0]
while count != n * (n - 1) // 2 and day <= 10 ** 4:
	L = [0 for i in range(n)]
	f1 = 0
	for i in range(n):
		if L[i] == 0 and ct[i] != n - 1:
			x = l[i][ct[i]]
			if l[x - 1][ct[x - 1]] - 1 == i and L[x - 1] == 0:
				ct[i] += 1
				ct[x - 1] += 1
				L[i] = 1
				L[x - 1] = 1
				count += 1
	day += 1
	check[0] = check[1]
	check[1] = count
	if check[0] == check[1]:
		print(-1)
		sys.exit()
if day > 10 ** 4:
	print(n * (n - 1) // 2)
	sys.exit()
print(day)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
A = [list([int(n) - 1 for n in input().split()]) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
	done = set()
	que2 = []
	for n in que:
		if n in done:
			continue
		pair = A[n][cur[n]]
		if pair in done:
			continue
		if n == A[pair][cur[pair]]:
			cur[n] += 1
			cur[pair] += 1
			done.add(n)
			done.add(pair)
			if cur[n] < N - 1:
				que2.append(n)
			if cur[pair] < N - 1:
				que2.append(pair)
	if len(done) > 0:
		ans += 1
	que = que2
ok = True
for i in range(N):
	if cur[i] < N - 1:
		ok = False
if ok:
	print(ans)
else:
	print(-1)


n = int(input())
import time
T = time.time()
data_set = [0 for i in range(n)]
for i in range(n):
	a = list(map(int, input().split()))
	a.append(-1)
	data_set[i] = a
index = [0 for i in range(n)]
ans = -1
flag = True
semi = False
now = [data_set[i][index[i]] for i in range(n)]
finished = [False for i in range(n)]
while flag:
	visited = [False for i in range(n)]
	sub = False
	for i in range(n):
		K = now[i]
		if now[K - 1] == i + 1 and (not (visited[i] or visited[K - 1])) and (not (finished[i] or finished[K - 1])):
			visited[i] = True
			visited[K - 1] = True
			index[i] += 1
			index[K - 1] += 1
			sub = True
			if index[i] == n - 1:
				finished[i] = True
			now[i] = data_set[i][index[i]]
			if index[K - 1] == n - 1:
				finished[K - 1] = True
			now[K - 1] = data_set[K - 1][index[K - 1]]
	if not sub:
		flag = False
	if time.time() - T > 1.5:
		flag = False
		semi = True
	ans += 1
judge = True
for i in range(n):
	if finished[i] == False:
		judge = False
		break
if judge:
	print(ans)
else:
	if not semi:
		print(-1)
	if semi:
		print(499500)


from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
sqrt = math.sqrt

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

def LF():
	return list(map(float, input().split()))

def LI_():
	return list([int(x) - 1 for x in input().split()])

def II():
	return int(input())

def IF():
	return float(input())

def LS():
	return list(map(list, input().split()))

def S():
	return list(input().rstrip())

def IR(n):
	return [II() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def FR(n):
	return [IF() for _ in range(n)]

def LFR(n):
	return [LI() for _ in range(n)]

def LIR_(n):
	return [LI_() for _ in range(n)]

def SR(n):
	return [S() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
import time

def A():
	s = S()
	t = S()
	ans = 0
	for i in range(3):
		if s[i] == t[i]:
			ans += 1
	print(ans)
	return

def B():
	(a, b) = LI()
	ans = 0
	b -= 1
	while b > 0:
		b -= a - 1
		ans += 1
	print(ans)
	return

def C():
	n = II()
	h = LI()
	i = 0
	ans = 0
	while i < n:
		down = i + 1
		while down < n:
			if h[down - 1] >= h[down]:
				down += 1
			else:
				break
		ans = max(ans, down - i - 1)
		i = down
	print(ans)
	return

def D():
	n = II()
	print(n * (n - 1) // 2)
	return

def E():
	start = time.time()
	n = II()
	a = LIR_(n)
	ans = 0
	tern = [0] * n
	while 1:
		ans += 1
		f = True
		c = defaultdict(int)
		for i in range(n):
			if c[i]:
				continue
			if tern[i] == n - 1:
				continue
			rival = a[i][tern[i]]
			if c[rival]:
				continue
			if tern[rival] == n - 1:
				continue
			if a[rival][tern[rival]] == i:
				c[i] += 1
				c[rival] += 1
				tern[rival] += 1
				tern[i] += 1
				f = False
		if time.time() - start >= 1.8:
			print(n * (n - 1) // 2)
			return
		if f:
			if tern == [n - 1] * n:
				print(ans - 1)
				return
			else:
				print(-1)
				return
	return

def F():
	return

def __starting_point():
	E()
__starting_point()


def f_e():
	n = int(input())
	a = [list(map(lambda x: int(x) - 1, input().split()))[::-1] for _ in range(n)]
	(q, bench, days) = (list(range(n)), [-1] * n, [0] * n)
	while q:
		i = q.pop(0)
		if not a[i]:
			continue
		you = a[i].pop()
		if bench[you] == i:
			days[i] = days[you] = max(days[i], days[you]) + 1
			bench[i] = bench[you] = -1
			q.append(i)
			q.append(you)
		else:
			bench[i] = you
	o = -1 if max(bench) >= 0 else max(days)
	print(o)
f_e()


N = int(input())
A = [[x - 1 for x in list(map(int, input().split()))] for i in range(N)]
days = 0
cand = set(range(N))
while True:
	games = set()
	for p in cand:
		if A[p] != []:
			if A[A[p][0]][0] == p:
				games.add(p)
				games.add(A[p][0])
	if not games:
		if any(A):
			print(-1)
			break
		else:
			print(days)
			break
	else:
		for i in games:
			A[i].pop(0)
	days += 1
	cand = games


import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())
N = next(read)
A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
days = 1
available_players = deque(range(1, N + 1))
next_opponent = [0] * (N + 1)
played = set()
while available_players:
	player = available_players.popleft()
	if not A[player]:
		continue
	opponent = A[player].popleft()
	if next_opponent[opponent] == player:
		available_players.append(player)
		available_players.append(opponent)
		next_opponent[player] = 0
		next_opponent[opponent] = 0
		if player in played:
			days += 1
			played = set()
		played.add(player)
		played.add(opponent)
	else:
		next_opponent[player] = opponent
for i in A:
	if len(i) > 0:
		print(-1)
		return
else:
	print(days)


from collections import deque

def main():
	N = int(input())
	A = [deque((int(a) - 1 for a in input().split())) for _ in range(N)]
	(P, W) = ([0] * N, [-1] * N)
	c = deque(range(N))
	while c:
		i = c.popleft()
		j = A[i].popleft()
		W[i] = j
		if W[j] == i:
			P[i] = P[j] = max(P[i], P[j]) + 1
			if A[i]:
				c.append(i)
			if A[j]:
				c.append(j)
	print(-1 if any((len(a) for a in A)) else max(P))
main()


from collections import deque
import sys
N = int(input())
match = []
for i in range(N):
	a = list(map(int, input().split()))
	match.append(a)
day = [0] * N
count = [0] * N
q = deque(range(N))
while q:
	p = q.popleft()
	if count[p - 1] < N - 1:
		enemy = match[p - 1][count[p - 1]]
		if p == match[enemy - 1][count[enemy - 1]]:
			today = max(day[p - 1], day[enemy - 1]) + 1
			day[p - 1] = today
			day[enemy - 1] = today
			count[p - 1] += 1
			count[enemy - 1] += 1
			q.append(p)
			q.append(enemy)
if min(count) != N - 1:
	print(-1)
else:
	print(max(day))


from collections import deque
import sys
input = sys.stdin.readline

def main():
	N = int(input())
	A = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
	ans = 0
	used_prev = set(range(N))
	while any(A):
		used = set()
		for i in used_prev:
			a = A[i]
			if not a or i in used:
				continue
			j = a[0]
			b = A[j]
			if not b or j in used:
				continue
			if i == b[0]:
				A[i].popleft()
				A[j].popleft()
				used.add(i)
				used.add(j)
		if not used:
			ans = -1
			break
		used_prev = used
		ans += 1
	print(ans)
main()


n = int(input())
a = []
for _ in range(n + 1):
	a.append([-1])
for i in range(n):
	inp = list(map(int, input().split()))
	for j in range(n - 2, -1, -1):
		a[i + 1].append(inp[j])
matched = [i for i in range(1, n + 1)]
finish = 0
days = 0
while True:
	used = set()
	while matched != []:
		i = matched.pop()
		p = a[i][-1]
		if p != -1 and a[p][-1] == i and (i not in used) and (p not in used):
			a[i].pop()
			a[p].pop()
			used.add(i)
			used.add(p)
			if a[i][-1] == -1:
				finish += 1
			if a[p][-1] == -1:
				finish += 1
	days += 1
	matched = list(used)
	if len(used) == 0:
		days = -1
		break
	elif finish == n:
		break
print(days)


from collections import deque
n = int(input())
a = [list(map(int, input().split())) + [0] for i in range(n)]
for i in range(n):
	for j in range(n):
		a[i][j] -= 1
l = [0] * n
d = [0] * n
Q = deque(range(n))
while Q:
	p = Q.popleft()
	q = a[p][l[p]]
	if a[q][l[q]] == p:
		m = max(d[p], d[q]) + 1
		d[p] = m
		d[q] = m
		l[p] += 1
		l[q] += 1
		Q.append(p)
		Q.append(q)
for i in l:
	if i != n - 1:
		exit(print(-1))
print(max(d))


from collections import defaultdict
n = int(input())
a = [[]]
for _ in range(n):
	tmp = [int(x) for x in input().split()]
	a.append(tmp[::-1])
p = [i for i in range(1, n + 1)]
c = defaultdict(int)
done = 0
for d in range(1, n * (n - 1) // 2 + 1):
	np = []
	for pp in p:
		if len(a[pp]) == 0:
			continue
		x = a[pp].pop()
		l = min(x, pp)
		r = max(x, pp)
		c[l, r] += 1
		if c[l, r] == 2:
			np.append(l)
			np.append(r)
			done += 1
	if done == n * (n - 1) // 2:
		print(d)
		exit()
	if len(np) == 0:
		print(-1)
		exit()
	p = np


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	N = int(readline())
	A = [[int(s) - 1 for s in reversed(readline().split())] for _ in range(N)]
	M = N * (N - 1) // 2
	games = 0
	players = set(range(N))
	for d in range(1, M + 1):
		(players, players_prev) = (set(), players)
		for i in players_prev:
			if not A[i] or i in players:
				continue
			j = A[i][-1]
			if j not in players and i == A[j][-1]:
				players.add(i)
				players.add(j)
				A[i].pop()
				A[j].pop()
				games += 1
		if games == M:
			print(d)
			break
		if not players:
			print(-1)
			break
	return

def __starting_point():
	main()
__starting_point()


def main():
	N = int(input())
	A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
	d = 0
	r = N
	cur = list(range(N))
	w = [a.pop() for a in A]
	while r:
		d += 1
		nxt = []
		for i in cur:
			o = w[i]
			if o == -1:
				continue
			if w[o] == i:
				nxt.append(i)
				nxt.append(o)
				w[i] = -1
				w[o] = -1
		if not nxt:
			return -1
		cur = []
		for i in nxt:
			if A[i]:
				w[i] = A[i].pop()
				cur.append(i)
			else:
				r -= 1
	return d
print(main())


def check(player):
	if not a[player]:
		return
	opponent = a[player][-1]
	if not a[opponent]:
		return
	if a[opponent][-1] == player:
		tpl = (player, opponent)
		q.add((min(tpl), max(tpl)))
n = int(input())
a = []
for _ in range(n):
	t = list(map(lambda x: int(x) - 1, input().split()))
	t.reverse()
	a.append(t)
q = set()
for i in range(n):
	check(i)
day = 0
while q:
	day += 1
	prev_q = set()
	(q, prev_q) = (prev_q, q)
	for (player, opponent) in prev_q:
		a[player].pop()
		a[opponent].pop()
	for (player, opponent) in prev_q:
		check(player)
		check(opponent)
if any((a[player] for player in range(n))):
	print(-1)
	exit()
print(day)


N = int(input())
A = [[0]]
for i in range(N):
	a = list(map(int, input().split()))
	a += [0]
	A.append(a)
B = [0 for i in range(N + 1)]
C = [a for a in range(1, N + 1)]
cnt = 0
for i in range(10 ** 6):
	D = []
	F = 0
	for j in C:
		if A[A[j][B[j]]][B[A[j][B[j]]]] == j and j not in D and (A[j][B[j]] not in D):
			D.append(j)
			D.append(A[j][B[j]])
			B[A[j][B[j]]] += 1
			B[j] += 1
			F = 1
			cnt += 1
	if F == 0:
		break
	D.sort()
	C = D
if cnt == N * (N - 1) // 2:
	print(i)
else:
	print(-1)


N = int(input())
A = [0 for i in range(N)]
for i in range(N):
	A[i] = [-1] + [int(c) - 1 for c in input().split()][::-1]

def f(cand):
	can_use = []
	candl = set()
	for i in cand:
		c = A[i][-1]
		if A[c][-1] == i:
			can_use += [i]
	for n in can_use:
		A[n].pop()
		candl.add(n)
		if A[n][-1] != -1:
			candl.add(A[n][-1])
	return (len(can_use), candl)
ans = 0
rest = N * (N - 1)
cand = set(range(N))
while True:
	ans += 1
	(x, cand) = f(cand)
	if x == 0:
		ans = -1
		break
	rest -= x
	if rest == 0:
		break
print(ans)


n = int(input())
a = {i + 1: list(map(int, input().split())) for i in range(n)}
ret = 1
pair = []
keys = a.keys()
while True:
	for k in keys:
		v = a[k][0]
		if a[v][0] == k:
			pair.append(k)
			if v not in keys:
				pair.append(v)
	for p in pair:
		if len(a[p]) > 1:
			a[p] = a[p][1:]
		else:
			a.pop(p)
	if len(a) == 0:
		break
	if len(pair) == 0:
		ret = -1
		break
	ret = ret + 1
	keys = [k for k in pair if k in a]
	pair = []
print(ret)


from collections import deque
N = int(input())
l = [deque([])] + [deque(map(int, input().split())) for _ in range(N)]
v = 0
ans = 0
t = N * (N - 1) // 2
last_used = set(range(1, N + 1))
while v < t and ans < t:
	used = set()
	for n in last_used:
		if n in used:
			continue
		if not l[n]:
			continue
		pair = l[n][0]
		b = l[pair][0]
		if pair in used:
			continue
		if b == n:
			l[n].popleft()
			l[pair].popleft()
			used |= {n, pair}
			v += 1
	last_used = used
	ans += 1
if ans == t and ans != v:
	print(-1)
else:
	print(ans)


from collections import deque
N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
l = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
day = 0
q = deque([(i + 1, a.pop()) for (i, a) in enumerate(A)])
while q:
	day += 1
	r = deque()
	while q:
		p = q.popleft()
		(x, y) = p
		if x > y:
			(x, y) = (y, x)
		l[x][y] += 1
		if l[x][y] >= 2:
			l[x][y] -= 2
			if A[x - 1]:
				r.append((x, A[x - 1].pop()))
			if A[y - 1]:
				r.append((y, A[y - 1].pop()))
	q = r
if all(map(len, A)):
	print(-1)
else:
	print(day)


def resolve():
	N = int(input())
	A = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
	cur = [0 for _ in range(N)]
	yesterday = set(range(N))
	rest = N * (N - 1)
	day = 0
	while len(yesterday) > 0 and rest > 0:
		today = set()
		totoday = set()
		for y in yesterday:
			o = A[y][cur[y]]
			if A[o][cur[o]] == y:
				today.add(o)
				today.add(y)
		for t in today:
			cur[t] += 1
			if cur[t] < N - 1:
				totoday.add(t)
		rest -= len(today)
		yesterday = totoday
		day += 1
	if rest == 0:
		print(day)
	else:
		print(-1)
resolve()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
A = [None] * N
for i in range(N):
	A[i] = [-1] + [int(x) - 1 for x in input().split()[::-1]]

def f(candi):
	played = []
	for n in candi:
		target = A[n][-1]
		if A[target][-1] == n:
			played.append(n)
	new_candi = set()
	for n in played:
		A[n].pop()
		new_candi.add(n)
		if A[n][-1] != -1:
			new_candi.add(A[n][-1])
	return (len(played), new_candi)
answer = 0
rest = N * (N - 1)
play_candi = set(range(N))
while True:
	answer += 1
	(x, play_candi) = f(play_candi)
	if x == 0:
		answer = -1
		break
	rest -= x
	if rest == 0:
		break
print(answer)


def solve():
	ans = 0
	N = int(input())
	stacks = [list(map(lambda x: int(x) - 1, input().split()))[::-1] for _ in range(N)]
	lis = [0] * N
	cnt = 0
	now = 0
	flag = 0
	while cnt < N * (N - 1) // 2:
		while not stacks[now]:
			now = (now + 1) % N
		a = stacks[now][-1]
		if not stacks[a]:
			return -1
		if stacks[a][-1] == now:
			lis[now] = max(lis[now], lis[a]) + 1
			lis[a] = lis[now]
			stacks[a].pop(-1)
			stacks[now].pop(-1)
			cnt += 1
			flag = 0
		else:
			now = a
			flag += 1
		if flag == N:
			return -1
	ans = max(lis)
	return ans
print(solve())


import collections
n = int(input())
a = [collections.deque((int(s) - 1 for s in input().split())) for _ in range(n)]
day = 0
players = set(range(n))
while any((v for v in a)):
	nxt_players = set()
	for player in players:
		if len(a[player]) == 0 or player in nxt_players:
			continue
		other = a[player][0]
		if len(a[other]) == 0 or other in nxt_players:
			continue
		if player == a[other][0]:
			a[player].popleft()
			a[other].popleft()
			nxt_players.add(player)
			nxt_players.add(other)
	if nxt_players:
		day += 1
		players = nxt_players
	else:
		print(-1)
		exit()
print(day)


from collections import deque
N = int(input())
ad = [[] for _ in range(N * N)]
num = [0] * (N * N)
for i in range(N):
	a = [int(e) - 1 for e in input().split()]
	for k in range(N - 2):
		j = a[k]
		nj = a[k + 1]
		v = N * max(i, j) + min(i, j)
		nv = N * max(i, nj) + min(i, nj)
		ad[v].append(nv)
		num[nv] += 1
S = deque()
L = []
for v in range(N * N):
	if num[v] == 0:
		S.append((v, 1))
while S:
	(v, d) = S.popleft()
	L.append(d)
	for nv in ad[v]:
		num[nv] -= 1
		if num[nv] == 0:
			S.append((nv, d + 1))
if len(L) != N * N:
	print(-1)
	exit()
ans = max(L)
print(ans)


import sys
N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
day = 0
cnt = N
Last = set([i for i in range(N)])
while cnt:
	flag = True
	Done = [False] * N
	L = set()
	for i in Last:
		if len(A[i]) == 0:
			continue
		if Done[i]:
			continue
		x = A[i][-1] - 1
		if A[x] and (not Done[x]) and (A[x][-1] - 1 == i):
			A[i].pop()
			A[x].pop()
			Done[i] = True
			Done[x] = True
			L.add(i)
			L.add(x)
			flag = False
			if not A[i]:
				cnt -= 1
			if not A[x]:
				cnt -= 1
	Last = L
	if flag:
		break
	day += 1
if cnt:
	print(-1)
else:
	print(day)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
n = int(readline())
a = [list(map(lambda x: int(x) - 1, readline().split())) for _ in range(n)]
q = list(range(n))
cnt = 0
while q:
	cnt += 1
	qq = set()
	while q:
		x = q.pop()
		if a[a[x][0]][0] == x:
			qq.add(x)
			qq.add(a[x][0])
	if qq:
		for x in qq:
			a[x].pop(0)
			if a[x]:
				q.append(x)
	else:
		print(-1)
		exit()
print(cnt)


import itertools
N = int(input())
A = [[int(_) - 1 for _ in input().split()][::-1] for _ in range(N)]
ans = 0
cand = list(range(N))
left = 1
while True:
	cand_ = set()
	for i in cand:
		v = A[i]
		if not len(v):
			continue
		if A[v[-1]][-1] == i:
			f = 0
			cand_.add(i)
			cand_.add(v[-1])
	if not cand_:
		break
	cand = cand_
	left = 0
	for i in cand:
		A[i].pop()
		left |= len(A[i]) > 0
	ans += 1
if left:
	print(-1)
else:
	print(ans)


def main():
	n = int(input())
	a = [list(map(int, input().split())) for _ in [0] * n]
	m = n * (n - 1) // 2
	d = dict()
	cnt = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			d[i, j] = cnt
			cnt += 1
	g = [[] for _ in [0] * m]
	gr = [0] * m
	for i in range(n):
		temp = []
		for j in a[i]:
			if i >= j:
				temp.append(d[j - 1, i])
			else:
				temp.append(d[i, j - 1])
		for (j, k) in enumerate(temp[1:]):
			g[temp[j]].append(k)
			gr[k] += 1
	q = [i for (i, j) in enumerate(gr) if j == 0]
	cnt = 0
	while q:
		cnt += 1
		qq = []
		for i in q:
			for j in g[i]:
				gr[j] -= 1
				if gr[j] == 0:
					qq.append(j)
		q = qq
	if sum(gr) == 0:
		print(cnt)
	else:
		print(-1)
main()


from collections import deque
a = int(input())
l = []
for i in range(a):
	tl = list(map(int, input().split()))
	tl = list(map(lambda x: x - 1, tl))
	l.append(tl)
q = deque(range(a))
days = [0] * a
pairs = [-1] * a
while q:
	x = q.popleft()
	if len(l[x]) == 0:
		continue
	y = l[x].pop(0)
	if pairs[y] == x:
		days[x] = days[y] = max(days[x], days[y]) + 1
		q.append(x)
		q.append(y)
	else:
		pairs[x] = y
if not any(l):
	print(max(days))
else:
	print(-1)


N = int(input())
A = [[]] + [list(map(int, input().split())) for _ in range(N)]
c = [0 for _ in range(N + 1)]
p = []
for i in range(1, N + 1):
	j = A[i][c[i]]
	if i == A[j][c[j]] and i < j:
		p.append((i, j))
ans = 0
while p:
	q = []
	for (i, j) in p:
		c[i] += 1
		c[j] += 1
		if c[i] < N - 1:
			k = A[i][c[i]]
			if A[k][c[k]] == i:
				q.append((i, k))
		if c[j] < N - 1:
			k = A[j][c[j]]
			if A[k][c[k]] == j:
				q.append((j, k))
	ans += 1
	p = q
ans = ans if all((c[i] == N - 1 for i in range(1, N + 1))) else -1
print(ans)


from collections import deque
import copy, sys
input = sys.stdin.readline
n = int(input())
a = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
q = deque()
pre_q = deque()
day = 0

def check(p, q):
	if not len(a[p]):
		return
	o = a[p][0]
	if p == a[o][0]:
		if p > o:
			(p, o) = (o, p)
		if not (p, o) in q:
			q.append((p, o))
fin = []
for p in range(n):
	if not p in fin:
		o = a[p][0]
		if p == a[o][0]:
			q.append((p, o))
			fin += [p, o]
while q:
	day += 1
	pre_q = copy.copy(q)
	q.clear()
	for (p, o) in pre_q:
		a[p].popleft()
		a[o].popleft()
		check(p, q)
		check(o, q)
if all(map(len, a)):
	print(-1)
else:
	print(day)


import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
r = set(list(range(n)))
N = n * (n - 1) // 2 + 1
for _ in range(N):
	if not r:
		print(_)
		break
	ne = set()
	flag = True
	for j in r:
		if not a[j]:
			continue
		c = a[j][0]
		if c == '-':
			continue
		if j + 1 == a[c - 1][0]:
			a[j][0] = '-'
			a[c - 1][0] = '-'
			ne.add(j)
			ne.add(c - 1)
	for j in list(ne):
		if a[j]:
			if a[j][0] == '-':
				a[j].pop(0)
				flag = False
				if not a[j]:
					ne.remove(j)
	if flag:
		print(-1)
		break
	else:
		r = ne


from collections import defaultdict
N = int(input())
A = [[0 for _ in range(N - 1)] for _ in range(N)]
for i in range(N):
	A[i] = [int(x) - 1 for x in input().split()]
day = 0
M = defaultdict(int)
for i in range(N):
	M[i] += 1
W = [0] * N
while M:
	day += 1
	for m in M:
		W[m] = A[m].pop(0) if A[m] else -1
	_M = defaultdict(int)
	for m in M:
		if W[m] >= 0 and W[W[m]] == m:
			_M[m] += 1
			_M[W[m]] += 1
	M = _M
for w in W:
	if w > 0:
		print(-1)
		break
else:
	print(day - 1)


N = int(input())
A = []
rem = N * (N - 1) // 2
for _ in range(N):
	(*temp,) = map(int, input().split())
	A.append(temp[::-1])
day = 0
next_opponent = [-1] * N
played_yesterday = list(range(N))
while rem:
	day += 1
	impossible = True
	for p in played_yesterday:
		if A[p]:
			next_opponent[p] = A[p].pop() - 1
	played_today = []
	for p in played_yesterday:
		candidate = next_opponent[p]
		if candidate == -1:
			continue
		elif next_opponent[candidate] == p:
			impossible = False
			rem -= 1
			played_today += [p, candidate]
			(next_opponent[p], next_opponent[candidate]) = (-1, -1)
	if impossible:
		print(-1)
		break
	played_yesterday = played_today
else:
	print(day)


from collections import deque

def main():
	n = int(input())
	a = [0] * n
	for i in range(n):
		a[i] = deque(list(map(lambda x: int(x) - 1, input().split())))
	q = deque([])
	tmp = set()
	for (idx, i) in enumerate(a):
		x = idx
		y = i[0]
		if x == a[y][0]:
			tmp.add(x)
			tmp.add(y)
	q = deque(tmp)
	for i in tmp:
		a[i].popleft()
	day = 0
	while True:
		day += 1
		t = q.copy()
		q = deque()
		tmp = set()
		while t:
			x = t.popleft()
			if len(a[x]) == 0:
				continue
			y = a[x][0]
			if x == a[y][0]:
				tmp.add(x)
				tmp.add(y)
		q = deque(tmp)
		for i in tmp:
			a[i].popleft()
		if len(q) == 0:
			break
	for i in range(n):
		if len(a[i]) != 0:
			print(-1)
			exit()
	print(day)
main()


from collections import deque, defaultdict
N = int(input())
A = [deque([int(a) - 1 for a in input().split()]) for _ in range(N)]
D = [0] * N
canBattle = defaultdict(lambda : False)
que = deque(list(range(N)))
while que:
	i = que.popleft()
	j = A[i][0]
	canBattle[i, j] = True
	if canBattle[j, i]:
		A[i].popleft()
		A[j].popleft()
		day = max(D[i], D[j])
		D[i] = D[j] = day + 1
		if A[i]:
			que.append(i)
		if A[j]:
			que.append(j)
if all((len(a) == 0 for a in A)):
	print(max(D))
else:
	print(-1)


from collections import deque
N = int(input())
matches = [[a - 1 for a in map(int, input().split())] for line in range(N)]
q = deque(range(N))
depth = [0] * N
waiting = [-1] * N
while q:
	a = q.popleft()
	b = matches[a].pop()
	if waiting[b] == a:
		depth[a] = depth[b] = max(depth[a], depth[b]) + 1
		if matches[a]:
			q.append(a)
		if matches[b]:
			q.append(b)
	else:
		waiting[a] = b
if any(matches):
	print(-1)
else:
	print(max(depth))


def main():
	n = int(input())
	a = [list([int(x) - 1 for x in input().split()]) for _ in range(n)]
	for i in range(n):
		a[i].reverse()
	s = set()

	def check(i, s):
		if len(a[i]) == 0:
			return
		j = a[i][-1]
		if len(a[j]) == 0:
			return
		if a[j][-1] == i:
			if i < j:
				s.add((i, j))
			else:
				s.add((j, i))
	for i in range(n):
		check(i, s)
	day = 0
	while s:
		day += 1
		prevS = set()
		(s, prevS) = (prevS, s)
		for p in prevS:
			i = p[0]
			j = p[1]
			a[i].pop()
			a[j].pop()
		for p in prevS:
			i = p[0]
			j = p[1]
			check(i, s)
			check(j, s)
	for i in range(n):
		if len(a[i]):
			print(-1)
			return
	print(day)
	return
main()


import sys
readline = sys.stdin.readline
N = int(readline())
A = [None] * N
for i in range(N):
	A[i] = list(map(lambda x: x - 1, map(int, readline().split())))[::-1]
candi = set(range(N))
day = 0
while candi:
	day += 1
	nex = set()
	done = set()
	for player in candi:
		if player in done:
			continue
		if len(A[player]) == 0:
			continue
		rival = A[player][-1]
		if rival in done:
			continue
		if A[rival][-1] == player:
			A[player].pop()
			A[rival].pop()
			if A[player]:
				nex.add(player)
			done.add(player)
			if A[rival]:
				nex.add(rival)
			done.add(rival)
	if len(done) == 0:
		print(-1)
		return
	candi = nex
print(day)


N = int(input())
A = [list([int(n) - 1 for n in input().split()]) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
	done = {}
	que2 = []
	for n in que:
		if done.get(n):
			continue
		pair = A[n][cur[n]]
		if done.get(pair):
			continue
		if n == A[pair][cur[pair]]:
			cur[n] += 1
			cur[pair] += 1
			done[n] = True
			done[pair] = True
			if cur[n] < N - 1:
				que2.append(n)
			if cur[pair] < N - 1:
				que2.append(pair)
	if len(done) > 0:
		ans += 1
	que = que2
ok = True
for i in range(N):
	if cur[i] < N - 1:
		ok = False
if ok:
	print(ans)
else:
	print(-1)


from collections import deque
N = int(input())
matches = [[int(x) - 1 for x in input().split()] for _ in range(N)]
q = deque(range(N))
days = [0] * N
pairs = [-1] * N
while q:
	a = q.popleft()
	match = matches[a]
	if not match:
		continue
	b = match.pop(0)
	if pairs[b] == a:
		days[a] = days[b] = max(days[a], days[b]) + 1
		q.append(a)
		q.append(b)
	else:
		pairs[a] = b
print(max(days) if not any(matches) else -1)


import sys
from collections import deque
n = int(input())
matches = [[a - 1 for a in map(int, line.split())] for line in sys.stdin]
q = deque(range(n))
depth = [0] * n
waiting = [-1] * n
while q:
	a = q.popleft()
	b = matches[a].pop()
	if waiting[b] == a:
		depth[a] = depth[b] = max(depth[a], depth[b]) + 1
		if matches[a]:
			q.appendleft(a)
		if matches[b]:
			q.appendleft(b)
	else:
		waiting[a] = b
if any(matches):
	print(-1)
else:
	print(max(depth))


from collections import deque
n = int(input())
A = []
for i in range(n):
	A.append([int(i) for i in input().split()])
nn = n * (n - 1) // 2
F = [[0] * (n + 1) for _ in range(n + 1)]
cur = 0
for i in range(1, n):
	for j in range(i + 1, n + 1):
		F[i][j] = cur
		F[j][i] = cur
		cur += 1
Edge = [[] for _ in range(nn)]
Deg = [0] * nn
for i in range(n):
	s = F[i + 1][A[i][0]]
	for j in range(1, n - 1):
		t = F[i + 1][A[i][j]]
		Edge[s].append(t)
		Deg[t] += 1
		s = t
ans = 0
S = [i for i in range(nn) if Deg[i] == 0]
D = deque()
DD = deque(S)
while DD:
	D = DD
	DD = deque()
	while D:
		d = D.popleft()
		for g in Edge[d]:
			Deg[g] -= 1
			if Deg[g] == 0:
				DD.append(g)
				S.append(g)
	ans += 1
print(-1 if len(S) < nn else ans)


from collections import defaultdict
N = int(input())
dic = defaultdict(list)
toNum = {}
L = N * (N - 1) // 2
s = [0]
for i in range(N - 1, 0, -1):
	s += [s[-1] + i]
dist = [0] * L
for i in range(N):
	inf = [int(c) - 1 for c in input().split()]
	pa = min(i, inf[0])
	pb = max(i, inf[0])
	pnum = s[pa] + (pb - pa - 1)
	for j in range(1, N - 1):
		a = min(i, inf[j])
		b = max(i, inf[j])
		num = s[a] + (b - a - 1)
		dic[pnum] += [num]
		dist[num] += 1
		pa = a
		pb = b
		pnum = num
hq = []
ans = 0
for i in range(L):
	if dist[i] == 0:
		hq += [i]
while hq:
	ans += 1
	nq = []
	for e in hq:
		for p in dic[e]:
			if dist[p] == 0:
				continue
			dist[p] -= 1
			if dist[p] == 0:
				nq += [p]
	hq = nq
if sum(dist) != 0:
	ans = -1
print(ans)


import time
start = time.time()
N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split())) for i in range(N)]
B = [0] * N
S = 0
ans = 0
while True:
	C = [0] * N
	for n in range(N):
		if C[n] == 0 and B[n] != N - 1:
			b = A[n][B[n]]
			if C[b] == 1:
				continue
			if A[b][B[b]] == n:
				B[n] += 1
				B[b] += 1
				(C[n], C[b]) = (1, 1)
	if sum(C) == 0:
		break
	ans += 1
	if time.time() - start > 1.7:
		print(N * (N - 1) // 2)
		exit()
print(ans if sum(B) == N * (N - 1) else -1)


import time
n = int(input())
al = [list(map(int, input().split())) for _ in range(n)]
m = n * (n - 1) // 2
tn = [n - 1] * n
start = time.time()
for i in range(m + 1):
	flg = True
	s = 0
	ts = set()
	for j in range(n):
		if tn[j] > 0 and j not in ts:
			t = al[j][0] - 1
			if t not in ts:
				if al[t][0] == j + 1:
					al[t].pop(0)
					tn[t] -= 1
					ts.add(t)
					al[j].pop(0)
					tn[j] -= 1
					flg = False
		ts.add(j)
		s += tn[j]
	if s == 0:
		print(i + 1)
		exit()
	if flg:
		print(-1)
		exit()
	now = time.time()
	if now - start > 1.6:
		print(m)
		exit()


import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
A = [deque(map(int, input().split())) for _ in range(N)]
q = []

def check(x):
	if len(A[x]) == 0:
		return
	tmp = A[x][0] - 1
	if A[tmp][0] - 1 == x:
		if tmp < x:
			(x, tmp) = (tmp, x)
		q.append((x, tmp))
		return
for i in range(N):
	check(i)
day = 0
while len(q) > 0:
	day += 1
	q = list(set(q))
	prevQ = []
	(prevQ, q) = (q, prevQ)
	for i in range(len(prevQ)):
		(x, y) = prevQ[i]
		A[x].popleft()
		A[y].popleft()
	for i in range(len(prevQ)):
		(x, y) = prevQ[i]
		check(x)
		check(y)
for i in range(N):
	if len(A[i]) != 0:
		print(-1)
		sys.exit()
print(day)


from collections import deque
N = int(input())
Ass = tuple((deque(map(int, input().split())) for _ in range(N)))
Q = set(range(N))
ans = -1
while Q:
	ans += 1
	Q2 = Q.copy()
	Q.clear()
	for i in Q2:
		if Ass[i]:
			t = Ass[i][0] - 1
			if Ass[t][0] == i + 1:
				Q.add(i)
				Q.add(t)
	for i in Q:
		Ass[i].popleft()
if any(Ass):
	print(-1)
else:
	print(ans)


import sys
N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split(' '))) for i in range(N)]
canUse = set(range(N))
ans = 0
done = 0
while done < N:
	ans += 1
	canUseNew = set()
	for n in canUse:
		if not A[n]:
			continue
		first = A[n][-1]
		if first in canUseNew or n in canUseNew:
			continue
		if A[first][-1] == n:
			A[n].pop()
			if len(A[n]) == 0:
				done += 1
			A[first].pop()
			if len(A[first]) == 0:
				done += 1
			canUseNew.add(n)
			canUseNew.add(first)
	if len(canUseNew) == 0:
		print(-1)
		sys.exit(0)
	canUse = canUseNew
print(ans)


from collections import deque
n = int(input())
matches = [list((a - 1 for a in map(int, input().split()))) for _ in range(n)]
q = deque(range(n))
depth = [0] * n
waiting = [-1] * n
while q:
	a = q.popleft()
	ma = matches[a]
	if not ma:
		continue
	b = ma.pop()
	if waiting[b] == a:
		depth[a] = depth[b] = max(depth[a], depth[b]) + 1
		q.append(a)
		q.append(b)
	else:
		waiting[a] = b
if any(matches):
	print(-1)
else:
	print(max(depth))


N = int(input())
A = []
for i in range(N):
	As = list(map(int, input().split()))
	As = list(reversed(list(map(lambda a: a - 1, As))))
	A.append(As)
d = 0
n = 0
l = list(range(N))
while True:
	n2 = 0
	l2 = []
	s2 = set()
	for i in l:
		if A[i] == []:
			continue
		j = A[i][-1]
		if A[j] == []:
			continue
		if i in s2 or j in s2:
			continue
		if A[j][-1] == i:
			n += 1
			n2 += 1
			s2.add(i)
			s2.add(j)
			l2.append(i)
			l2.append(j)
			A[i].pop()
			A[j].pop()
	if n2 == 0:
		if n == N * (N - 1) // 2:
			break
		print(-1)
		exit()
	l = l2
	d += 1
print(d)


import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
	n = int(input())

	def label(a, b):
		if a > b:
			(a, b) = (b, a)
		return (a - 1) * (2 * n - a) // 2 + b - a - 1
	m = n * (n - 1) // 2
	g = [[] for _ in range(m)]
	deg = [0] * m
	for i in range(1, n + 1):
		l = list(map(int, input().split()))
		for (x, y) in zip(l, l[1:]):
			t = label(i, y)
			g[label(i, x)].append(t)
			deg[t] += 1
	depth = [None] * m
	q = deque()
	ans = 1
	for (i, d) in enumerate(deg):
		if not d:
			depth[i] = 1
			q.append(i)
	while q:
		cur = q.popleft()
		for nxt in g[cur]:
			deg[nxt] -= 1
			if not deg[nxt]:
				depth[nxt] = depth[cur] + 1
				if ans < depth[nxt]:
					ans = depth[nxt]
				q.append(nxt)
	print(ans if all(depth) else -1)
main()


import sys
input = sys.stdin.readline
N = int(input().strip())
M = N * (N - 1) // 2
graph = [[] for i in range(M)]
in_cnt = [0 for i in range(M)]
for x in range(1, N + 1):
	l = list(map(int, input().split()))
	y = l[0]
	(b, s) = (max(x, y), min(x, y))
	prev = (b - 1) * (b - 2) // 2 + s - 1
	for y in l[1:]:
		(b, s) = (max(x, y), min(x, y))
		now = (b - 1) * (b - 2) // 2 + s - 1
		graph[prev].append(now)
		in_cnt[now] += 1
		prev = now
d = [1 for k in range(M)]
q = [i for i in range(M) if not in_cnt[i]]
if not q:
	print(-1)
	exit()
ans = 0
while q:
	x = q.pop()
	for y in graph[x]:
		d[y] = max(d[y], d[x] + 1)
		ans = max(ans, d[y])
		in_cnt[y] -= 1
		if not in_cnt[y]:
			q.append(y)
if [i for i in range(M) if in_cnt[i]]:
	print(-1)
	exit()
print(ans)


from collections import deque
N = int(input())

def trans(x):
	return int(x) - 1
A = deque()
for _ in range(N):
	A.append(deque(map(trans, input().split())))
Q = set()

def check(i):
	if len(A[i]) == 0:
		return
	j = A[i][0]
	if len(A[j]) == 0:
		return
	if A[j][0] == i:
		if i > j:
			(i, j) = (j, i)
		Q.add((i, j))
for i in range(N):
	check(i)
ans = 0
while len(Q) > 0:
	ans += 1
	Q2 = Q.copy()
	Q = set()
	for q in Q2:
		A[q[0]].popleft()
		A[q[1]].popleft()
	for q in Q2:
		check(q[0])
		check(q[1])
for i in range(N):
	if len(A[i]) > 0:
		print(-1)
		exit()
print(ans)


import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():
	n = int(input())
	A = []
	for _ in range(n):
		t = deque(list([int(x) - 1 for x in input().split()]))
		A.append(t)
	que = deque(list(range(n)))
	res = 0
	emp = [False] * n
	while que:
		next_que = deque([])
		check = set()
		while que:
			i = que.popleft()
			if A[i]:
				idx = A[i][0]
				if i not in check and idx not in check and (A[idx][0] == i):
					A[i].popleft()
					A[idx].popleft()
					next_que.append(i)
					next_que.append(idx)
					check.add(i)
					check.add(idx)
			else:
				emp[i] = True
		que = next_que
		if que:
			res += 1
	else:
		print(res if all(emp) else -1)

def __starting_point():
	resolve()
__starting_point()


def solve():
	N = int(input())
	Ass = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
	day = 0
	numMatch = 0
	ps = set(range(N))
	isReadys = [0] * N
	iAs = [-1] * N
	while True:
		day += 1
		p2s = set()
		for p in ps:
			iAs[p] += 1
			if iAs[p] == N - 1:
				continue
			q = Ass[p][iAs[p]]
			if isReadys[q] and Ass[q][iAs[q]] == p:
				isReadys[q] = 0
				p2s.add(p)
				p2s.add(q)
				numMatch += 1
			else:
				isReadys[p] = 1
		if numMatch >= N * (N - 1) // 2:
			print(day)
			break
		if not p2s:
			print(-1)
			break
		ps = p2s
solve()


from collections import deque
import time
start = time.time()
n = int(input())
target_num = n * (n - 1) // 2
all_set = set()
a = [deque(list(map(int, input().split()))) for i in range(n)]
ans = 0
while True:
	cur_set = set()
	flag = False
	for i in range(n):
		if len(a[i]):
			tup = (min(i + 1, a[i][0]), max(i + 1, a[i][0]))
		else:
			continue
		if tup not in cur_set:
			cur_set.add(tup)
		elif tup in cur_set:
			all_set.add(tup)
			(t1, t2) = tup
			a[t1 - 1].popleft()
			a[t2 - 1].popleft()
			flag = True
	ans += 1
	if len(all_set) == target_num:
		break
	if time.time() - start > 1.8:
		print(1000 * 999 // 2)
		exit()
	if not flag:
		print(-1)
		exit()
print(ans)


from collections import deque
from typing import List, Optional, Tuple

def cycle_detectable_topological_sort(graph: List[List[int]], in_degrees: List[int], first_index: int=0) -> Tuple[Optional[List[int]], Optional[List[int]]]:
	V = len(graph) + first_index
	depths = [0] * V
	order = [i for i in range(first_index, V) if not in_degrees[i]]
	queue = deque(order)
	while queue:
		u = queue.popleft()
		cur_depth = depths[u]
		for v in graph[u]:
			in_degrees[v] -= 1
			if not in_degrees[v]:
				depths[v] = cur_depth + 1
				(queue.append(v), order.append(v))
	return (order, depths) if len(order) + first_index == V else (None, None)

def abc139_e():
	(N, *A) = list(map(int, open(0).read().split()))
	ids = [[-1] * (N + 1) for _ in range(N + 1)]
	cur_id = 0
	for i in range(1, N + 1):
		for j in range(i + 1, N + 1):
			ids[i][j] = ids[j][i] = cur_id
			cur_id += 1
	graph = [[] for _ in range(N * (N - 1) // 2)]
	in_degrees = [0] * (N * (N - 1) // 2)
	for (i, a) in enumerate(zip(*[iter(A)] * (N - 1)), 1):
		source = -1
		for j in a:
			target = ids[i][j]
			if source != -1:
				graph[source].append(target)
				in_degrees[target] += 1
			source = target
	(_, depths) = cycle_detectable_topological_sort(graph, in_degrees)
	print(max(depths) + 1 if depths else -1)

def grl_4_a():
	(V, _, *ST) = list(map(int, open(0).read().split()))
	graph = [[] for _ in range(V)]
	in_degrees = [0] * V
	for (s, t) in zip(*[iter(ST)] * 2):
		graph[s].append(t)
		in_degrees[t] += 1
	(res, _) = cycle_detectable_topological_sort(graph, in_degrees)
	print(1 if res is None else 0)

def __starting_point():
	abc139_e()
__starting_point()


from collections import deque

def is_not_empty(A):
	for x in A:
		if x:
			return True
	return False
N = int(input())
A = [deque([int(i) - 1 for i in input().split()]) for _ in range(N)]
ans = 0
yesterday = set(range(N))
while is_not_empty(A):
	today = set()
	for my in yesterday:
		if not A[my]:
			continue
		if my in today:
			continue
		enemy = A[my][0]
		if my == A[enemy][0] and enemy not in today:
			today.add(A[my].popleft())
			today.add(A[enemy].popleft())
	if not today:
		ans = -1
		break
	ans += 1
	yesterday = today
print(ans)


import sys
from collections import deque
input = lambda : sys.stdin.readline().rstrip()

def solve():
	N = int(input())
	A = [deque for _ in range(N)]
	for i in range(N):
		A[i] = deque(list([int(x) - 1 for x in input().split()]))
	days = 0
	ta = [i for i in range(N)]
	while True:
		ta2 = []
		aset = set()
		for i in ta:
			if len(A[i]) == 0 or i in aset:
				continue
			if i == A[A[i][0]][0]:
				ta2.append(i)
				ta2.append(A[i][0])
				aset |= set([i])
				aset |= set([A[i][0]])
		if len(ta2) > 0:
			for t in ta2:
				A[t].popleft()
			days += 1
			ta = ta2
		else:
			break
	empty = True
	for i in range(N):
		if len(A[i]) != 0:
			empty = False
			break
	if empty:
		print(days)
	else:
		print(-1)

def __starting_point():
	solve()
__starting_point()


N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
indices = [0] * N

def next(i):
	return A[i][indices[i]] if indices[i] < N - 1 else -1
from collections import deque
q = deque()
for i in range(N):
	j = next(i)
	if i < j and next(j) == i:
		q.append((i, j))
m = N * (N - 1) // 2
days = 0
while q:
	days += 1
	nq = deque()
	while q:
		(i, j) = q.pop()
		m -= 1
		indices[i] += 1
		indices[j] += 1
		ni = next(i)
		nj = next(j)
		if ni >= 0 and next(ni) == i:
			nq.append((i, ni))
		if nj >= 0 and nj != i and (next(nj) == j):
			nq.append((j, nj))
	q = nq
if m > 0:
	print(-1)
else:
	print(days)


N = int(input())
G = [list(map(int, input().split())) for _ in range(N)]
cur = [0] * N
edge = [0] * N
for i in range(N):
	edge[i] = G[i][0] - 1
day = 0
player = set(range(N))
cnt = 0
while len(player) > 0:
	day += 1
	game = set()
	for i in player:
		e = edge[i]
		if i == edge[e] and i != e:
			game.add(i)
			game.add(e)
	player = set()
	for j in game:
		cur[j] += 1
		c = cur[j]
		if c >= N - 1:
			edge[j] = j
		else:
			edge[j] = G[j][c] - 1
			player.add(j)
if min(cur) != N - 1:
	ans = -1
else:
	ans = day
print(ans)


import collections
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
arr = [0] + [collections.deque(arr[i]) for i in range(n)]
ans = 0
cand = set(range(1, n + 1))
while 1:
	check = set()
	for i in cand:
		if not arr[i]:
			continue
		pair = arr[i][0]
		if arr[pair][0] == i:
			check.add(i)
			check.add(pair)
	if not check:
		break
	cand = set()
	for i in check:
		cand.add(i)
		arr[i].popleft()
		if arr[i]:
			cand.add(arr[i][0])
	ans += 1
for i in range(1, n + 1):
	if arr[i]:
		print(-1)
		break
else:
	print(ans)


n = int(input())
from collections import deque
a = [None] * (n + 1)
for i in range(1, n + 1):
	a_tmp = tuple(map(int, input().split()))
	a[i] = deque(a_tmp)
d = deque(range(1, n + 1))
ans = 0
games = 0
while True:
	players = set()
	while d:
		tmp = d.pop()
		next = a[tmp][0]
		if a[next][0] == tmp:
			players.add(tmp)
			players.add(next)
	if len(players) == 0:
		break
	for i in players:
		games += 1
		a[i].popleft()
		if a[i]:
			d.append(i)
	ans += 1
if games == n * (n - 1):
	print(ans)
else:
	print(-1)


from collections import deque
n = int(input())
match = [deque([int(i) - 1 for i in input().split()]) for _ in range(n)]
q = deque(range(n))
wait = [-1] * n
finish_day = [0] * n
match_count = 0
while q:
	x = q.popleft()
	y = match[x].popleft()
	if wait[y] != x:
		wait[x] = y
	else:
		match_count += 1
		match_day = max(finish_day[x], finish_day[y]) + 1
		finish_day[x] = finish_day[y] = match_day
		(wait[x], wait[y]) = (-1, -1)
		if match[x]:
			q.append(x)
		if match[y]:
			q.append(y)
if match_count != n * (n - 1) / 2:
	print(-1)
else:
	print(max(finish_day))


N = int(input())
X = [[int(a) - 1 for a in input().split()] for _ in range(N)]
Y = [0] * N
Z = [-1] * N
L = [a for a in range(N)]
f = 1
d = 0
c = 0
while f:
	d += 1
	f = 0
	NL = []
	for l in L:
		(a, aa) = (Y[l], Z[l])
		if a >= N - 1:
			continue
		ll = X[l][a]
		(b, bb) = (Y[ll], Z[ll])
		if b >= N - 1:
			continue
		lll = X[ll][b]
		if lll == l and aa < d and (bb < d):
			f = 1
			c += 1
			Y[l] += 1
			Z[l] = d
			if Y[l] < N - 1:
				NL.append(l)
			Y[ll] += 1
			Z[ll] = d
			if Y[ll] < N - 1:
				NL.append(ll)
	if c == N * (N - 1) // 2:
		print(d)
		break
	L = NL
else:
	print(-1)


from collections import deque
N = int(input())
A = [list([int(x) - 1 for x in input().split()])[::-1] for _ in range(N)]
q = deque([])

def check(i, q):
	if len(A[i]) == 0:
		return
	j = A[i][-1]
	if len(A[j]) == 0:
		return
	if A[j][-1] == i:
		if i > j:
			(i, j) = (j, i)
		q.append((i, j))
	return
for i in range(N):
	check(i, q)
day = 0
while q:
	day += 1
	q = set(sorted(q))
	prev = deque([])
	(prev, q) = (q, prev)
	for (i, j) in prev:
		A[i].pop(-1)
		A[j].pop(-1)
	for (i, j) in prev:
		check(i, q)
		check(j, q)
for i in range(N):
	if len(A[i]) != 0:
		print(-1)
		return
print(day)


min2 = lambda x, y: x if x < y else y
N = int(input())
queues = [list(map(lambda x: int(x) - 1, input().split()))[::-1] for _ in range(N)]
q = set()
for (i, l) in enumerate(queues):
	if i < l[-1] and queues[l[-1]][-1] == i:
		q.add(i)
d = 0
while q:
	possible = set()
	for v in q:
		u = queues[v].pop()
		queues[u].pop()
		possible.add(v)
		possible.add(u)
	q.clear()
	for v in possible:
		try:
			u = queues[v][-1]
			if queues[u][-1] == v:
				q.add(min2(u, v))
		except IndexError:
			pass
	d += 1
print(-1 if any((l for l in queues)) else d)


import sys
N = int(input())
amat = [[-1]]
for i in range(N):
	alist = list(map(int, input().split()))
	amat.append(list(reversed(alist)))
cleared_num = 0
new_search_index = set(range(1, N + 1))
for answer in range(1, N ** 3):
	matched_set = set()
	unchanged = True
	search_index = new_search_index
	new_search_index = set()
	for i in search_index:
		if i in matched_set:
			continue
		ai_next = amat[i][-1]
		if amat[ai_next][-1] == i and (not ai_next in matched_set):
			matched_set.add(amat[i].pop())
			matched_set.add(amat[ai_next].pop())
			if len(amat[i]) == 0:
				cleared_num += 1
			else:
				new_search_index.add(i)
			if len(amat[ai_next]) == 0:
				cleared_num += 1
			else:
				new_search_index.add(ai_next)
			unchanged = False
	if unchanged:
		print(-1)
		return
	elif cleared_num == N:
		print(answer)
		return


n = int(input())
e = [[] for _ in range(n * n)]
co = [0] * (n * n)
for i in range(n):
	a = [int(i) - 1 for i in input().split()]
	for j in range(n - 2):
		(aa, bb) = (min(i, a[j]), max(i, a[j]))
		(cc, dd) = (min(i, a[j + 1]), max(i, a[j + 1]))
		e[aa * n + bb].append(cc * n + dd)
		co[cc * n + dd] += 1
x = []
for i in range(n * n):
	if co[i] == 0:
		x.append(i)
ans = 0
while x:
	y = []
	for i in x:
		for j in e[i]:
			co[j] -= 1
			if co[j] == 0:
				y.append(j)
	x = y
	ans += 1
if max(co) > 0:
	print(-1)
else:
	print(ans)


from collections import deque
from typing import List

def get_longest_path_depth(graph: List[List[int]], in_degrees: List[int], first_index: int=0) -> int:
	V = len(graph) + first_index
	queue = deque()
	depths = [-1] * V
	for i in range(first_index, V):
		if not in_degrees[i]:
			queue.append(i)
			depths[i] = 0
	while queue:
		u = queue.popleft()
		cur_depth = depths[u]
		for v in graph[u]:
			in_degrees[v] -= 1
			if not in_degrees[v]:
				depths[v] = max(depths[v], cur_depth + 1)
				queue.append(v)
	return max(depths[first_index:]) if min(depths[1:]) != -1 else -1

def abc139_e():
	(N, *A) = list(map(int, open(0).read().split()))
	ids = [[-1] * (N + 1) for _ in range(N + 1)]
	cur_id = 0
	for i in range(1, N + 1):
		for j in range(i + 1, N + 1):
			ids[i][j] = ids[j][i] = cur_id
			cur_id += 1
	graph = [[] for _ in range(N * (N - 1) // 2)]
	in_degrees = [0] * (N * (N - 1) // 2)
	for (i, a) in enumerate(zip(*[iter(A)] * (N - 1)), 1):
		source = -1
		for j in a:
			target = ids[i][j]
			if source != -1:
				graph[source].append(target)
				in_degrees[target] += 1
			source = target
	depth = get_longest_path_depth(graph, in_degrees)
	print(depth + 1 if depth != -1 else -1)

def __starting_point():
	abc139_e()
__starting_point()


n = int(input())
a = [[int(x) - 1 for x in input().split()] for _ in range(n)]
cnt = 0
id = [[0] * n for _ in range(n)]
for i in range(n):
	for j in range(i + 1, n):
		id[i][j] = cnt
		cnt += 1

def toid(x, y):
	return id[x][y] if x < y else id[y][x]
for i in range(n):
	for j in range(n - 1):
		a[i][j] = toid(i, a[i][j])
nedge = n * (n - 1) // 2
g = [[] for _ in range(nedge)]
to = [0] * nedge
for i in range(n):
	for j in range(1, n - 1):
		g[a[i][j - 1]].append(a[i][j])
		to[a[i][j]] += 1
from collections import deque
dp = [1] * nedge
q = deque([])
cnt = 0
for i in range(nedge):
	if to[i] == 0:
		q.append(i)
		cnt += 1
ans = 1
while q:
	e = q.popleft()
	for ne in g[e]:
		dp[ne] = max(dp[ne], dp[e] + 1)
		to[ne] -= 1
		if to[ne] == 0:
			q.append(ne)
			cnt += 1
	ans = max(ans, dp[e])
if cnt != nedge:
	print(-1)
else:
	print(ans)


from sys import setrecursionlimit as SRL, stdin
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : map(int, rd().strip().split())
q = [[]]
l = [0] * 1005
d = [0] * 1005
hv = [0] * 1005

def dfs(x, y):
	hv[x] = 1
	for i in range(l[x], n - 1):
		if q[x][i] == y:
			l[x] = i + 1
			hv[x] = 0
			d[q[x][i]] += 1
			d[x] += 1
			d[x] = max(d[x], d[q[x][i]])
			d[q[x][i]] = max(d[x], d[q[x][i]])
			return
		if hv[q[x][i]]:
			print(-1)
			exit(0)
		dfs(q[x][i], x)
		d[x] = max(d[q[x][i]], d[x])
	hv[x] = 0
	l[x] = n
n = int(input())
for i in range(n):
	a = list(rrd())
	q.append(a)
for i in range(1, n + 1):
	dfs(i, 0)
print(max(d))


from collections import defaultdict
n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]
adj = defaultdict(list)
in_deg = defaultdict(int)
for (u, row) in enumerate(a, 1):
	for (v1, v2) in zip(row, row[1:]):
		(uu1, vv1) = (min(u, v1), max(u, v1))
		(uu2, vv2) = (min(u, v2), max(u, v2))
		match1 = uu1 + vv1 * 1000
		match2 = uu2 + vv2 * 1000
		adj[match1].append(match2)
		in_deg[match1]
		in_deg[match2] += 1
now = [key for (key, val) in in_deg.items() if val == 0]
day = 0
while now:
	day += 1
	nxt = []
	for u in now:
		for v in adj[u]:
			in_deg[v] -= 1
			if in_deg[v] == 0:
				nxt.append(v)
	now = nxt
if max(in_deg.values()) > 0:
	day = -1
print(day)


N = int(input())
aaa = []
for i in range(N):
	aaa.append(list(reversed(list(map(int, input().split())))))
cs = set(range(N))
for i in range(0, N * N + 1):
	empty = True
	played = False
	ncs = set()
	for j in cs:
		aa = aaa[j]
		if len(aa) > 0:
			empty = False
			l = aa[-1] - 1
			if j not in ncs and l not in ncs and (len(aaa[l]) > 0) and (aaa[l][-1] == j + 1):
				aa.pop()
				aaa[l].pop()
				played = True
				ncs.add(j)
				ncs.add(l)
	cs = ncs
	if empty:
		print(i)
		break
	elif not played:
		print(-1)
		break


N = int(input())
A = []
for i in range(N):
	temp = list(map(int, input().split()))
	for j in range(N - 1):
		temp[j] -= 1
	A.append(temp)
cand = list(range(N))
cur = [0] * N
goal = 0
day = 0
while goal < N:
	day += 1
	game = []
	new_cur = cur[:]
	for i in cand:
		if i in game or cur[i] == N - 1:
			continue
		opponent = A[i][cur[i]]
		if A[opponent][cur[opponent]] == i:
			new_cur[i] += 1
			new_cur[opponent] += 1
			game.append(i)
			game.append(opponent)
			if new_cur[i] == N - 1:
				goal += 1
			if new_cur[opponent] == N - 1:
				goal += 1
	cand = game
	cur = new_cur
	if not game:
		print(-1)
		exit()
print(day)


from collections import deque

def solve():
	n = int(input())
	a = []
	for i in range(n):
		ai = [int(j) - 1 for j in input().split()]
		a.append(deque(ai))
	d = set()
	q = deque()
	for i in range(n):
		ai = a[i].popleft()
		if i < ai:
			q.append((i, ai))
		else:
			q.append((ai, i))
	ans = 0
	while q:
		ans += 1
		nxt_q = deque()
		while q:
			(i, ai) = q.pop()
			if (i, ai) in d:
				if a[i]:
					ni = a[i].popleft()
					if i < ni:
						nxt_q.append((i, ni))
					else:
						nxt_q.append((ni, i))
				if a[ai]:
					ni = a[ai].popleft()
					if ai < ni:
						nxt_q.append((ai, ni))
					else:
						nxt_q.append((ni, ai))
			else:
				d.add((i, ai))
		q = nxt_q
	if any((i for i in a)):
		ans = -1
	print(ans)
solve()


import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
league = [0] * (n + 1)
cnt = 0
while True:
	topop = []
	if cnt == 0:
		for (i, player) in enumerate(a):
			x = player[-1]
			if league[x] == i + 1:
				topop.append(x)
				topop.append(i + 1)
			else:
				league[i + 1] = x
	else:
		for player in popped:
			if a[player - 1] == []:
				continue
			x = a[player - 1][-1]
			if league[x] == player:
				topop.append(x)
				topop.append(player)
			else:
				league[player] = x
	popped = []
	if topop == []:
		print(-1)
		return
	for t in topop:
		if a[t - 1] == []:
			print(-1)
			return
		a[t - 1].pop()
		popped.append(t)
	cnt += 1
	if not any((a[i] for i in range(n))):
		break
print(cnt)


import sys
import collections
from collections import defaultdict
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

def main():
	N = int(input())
	A = [[int(x) for x in input().split()] for _ in range(N)]
	q = [collections.deque() for j in range(N)]
	for (i, a) in enumerate(A):
		for aa in a:
			q[i].append(aa)
	ans = 0
	current = defaultdict(int)
	for (i, v) in enumerate(q):
		current[i + 1] = v[0]
	while True:
		v = set()
		for k in list(current.keys()):
			if k == q[current[k] - 1][0]:
				v.add(k)
				v.add(current[k])
		current = defaultdict(int)
		if len(v) == 0:
			break
		for vv in v:
			q[vv - 1].popleft()
			if len(q[vv - 1]):
				current[vv] = q[vv - 1][0]
		ans += 1
	size = 0
	for i in range(N):
		size += len(q[i])
	if size == 0:
		print(ans)
	else:
		print(-1)

def __starting_point():
	main()
__starting_point()


from collections import deque
n = int(input())
a_list = []
for i in range(n):
	a_list.append(deque([int(aa) - 1 for aa in input().split()]))
day = 0
battle = 0
for _ in range(n * (n - 1) // 2):
	if battle == n * (n - 1) // 2:
		break
	day += 1
	battle_today = 0
	tomorrow = set([])
	if day == 1:
		player = set([i for i in range(n)])
	for i in player:
		if len(a_list[i]) == 0:
			continue
		j = a_list[i][0]
		if (i == a_list[j][0]) & (j not in tomorrow) & (len(a_list[j]) > 0) & (i not in tomorrow):
			tomorrow.add(i)
			tomorrow.add(a_list[i][0])
			battle += 1
			battle_today += 1
			a_list[i].popleft()
			a_list[j].popleft()
	player = tomorrow
	if battle_today == 0:
		day = -1
		break
print(day)


from copy import deepcopy
from heapq import heappop, heappush
n = int(input())
a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
d = [0] * n
ans = 0
temp = []
for x in range(n):
	heappush(temp, x)
while 1:
	next_temp = []
	while len(temp) > 0:
		x = heappop(temp)
		if d[x] >= n - 1:
			continue
		y = a[x][d[x]]
		if y not in next_temp:
			if a[y][d[y]] == x:
				heappush(next_temp, x)
				heappush(next_temp, y)
	for t in next_temp:
		d[t] += 1
	if len(next_temp) == 0:
		break
	temp = [] + next_temp
	ans += 1
if d.count(n - 1) == n:
	print(ans)
else:
	print(-1)


from collections import deque, defaultdict
N = int(input())
A = [deque(map(lambda a: int(a) - 1, input().split())) for _ in range(N)]
D = [0] * N
Nx = [-1] * N
que = deque(range(N))
while que:
	i = que.popleft()
	j = A[i].popleft()
	Nx[i] = j
	if Nx[j] == i:
		day = max(D[i], D[j])
		D[i] = D[j] = day + 1
		if A[i]:
			que.append(i)
		if A[j]:
			que.append(j)
if all((len(a) == 0 for a in A)):
	print(max(D))
else:
	print(-1)


from collections import deque
import time
zuru = time.time()
N = int(input())
A = [deque(map(int, input().split())) for _ in range(N)]
match = 0
que = [0 for _ in range(N + 1)]
for day in range(1, (N - 1) * N // 2 + 1):
	tsumi = True
	for i in range(1, N + 1):
		if que[i] == 0 and A[i - 1] != deque():
			que[i] = A[i - 1].popleft()
	for i in range(1, N + 1):
		if que[i] != 0 and que[que[i]] == i:
			que[que[i]] = 0
			que[i] = 0
			match += 1
			tsumi = False
	if tsumi:
		ans = -1
		break
	if match == (N - 1) * N / 2:
		ans = day
		break
	if time.time() - zuru > 1.5:
		ans = N * (N - 1) // 2
		break
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
a = [[i - 1 for i in map(int, input().split())][::-1] for j in range(n)]

def check(i):
	if a[i] == []:
		return
	elif a[a[i][-1]][-1] == i:
		q.add((min(a[i][-1], i), max(a[i][-1], i)))
q = set()
for i in range(n):
	check(i)
d = 0
while q:
	d += 1
	pq = set()
	(pq, q) = (q, pq)
	for i in pq:
		del a[i[0]][-1], a[i[1]][-1]
		check(i[0])
		check(i[1])
for i in a:
	if i != []:
		print(-1)
		exit()
print(d)


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
g = [set() for _ in range(n * (n - 1) // 2 + 1)]
visit = [0] * (n * (n - 1) // 2 + 1)
d = [0] * (n * (n - 1) // 2 + 1)
for i in range(1, n + 1):
	last = 0
	for j in list(map(int, input().split())):
		(mi, ma) = (min(i - 1, j - 1), max(i - 1, j - 1))
		current = ma * (ma - 1) // 2 + mi + 1
		g[last].add(current)
		last = current

def dfs(u):
	if visit[u] == 2:
		return d[u]
	ans = 0
	visit[u] = 1
	for v in g[u]:
		if visit[v] == 1:
			print(-1)
			exit(0)
		d[u] = max(d[u], 1 + dfs(v))
	visit[u] = 2
	return d[u]
print(dfs(0))


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

def c(x, y):
	if y < x:
		(x, y) = (y, x)
	return x * n + y
e = [[] for i in range(n ** 2)]
count = [0] * n ** 2
for i in range(n):
	for j in range(n - 2):
		y = c(i, a[i][j] - 1)
		z = c(i, a[i][j + 1] - 1)
		count[z] += 1
		e[y].append(z)
q = []
for i in range(n - 1):
	for j in range(i + 1, n):
		x = c(i, j)
		if count[x] == 0:
			q.append(x)
ans = 0
while q:
	ans += 1
	old = q
	q = []
	for nowq in old:
		for nex in e[nowq]:
			count[nex] -= 1
			if count[nex] == 0:
				q.append(nex)
if sum(count) > 0:
	print(-1)
else:
	print(ans)


N = int(input())
A = [list(map(int, input().split())) for n in range(N)]
P = [0] * N

def get_num(i):
	return A[i][P[i]] - 1

def update(mem, K):
	for i in mem:
		P[i] += 1
		if P[i] == N - 1:
			K.remove(i)

def f():
	K = {i for i in range(N)}
	L = {i for i in range(N)}
	mem = set()
	for t in range(N * (N - 1) // 2 + 1):
		if len(K) == 0:
			return t
		for i in L:
			if i in mem:
				continue
			j = get_num(i)
			if j in mem:
				continue
			if i == get_num(j):
				mem.add(i)
				mem.add(j)
		if len(mem) == 0:
			return -1
		update(mem, K)
		L = K & mem
		mem.clear()
	return -2
print(f())


import time
start = time.time()
N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split())) for i in range(N)]
B = [0] * N
days = 0
games_amount = 0
for i in range(N * (N - 1) // 2):
	games = 0
	played = set()
	for j in range(N):
		if len(A[j]) == 0 or j in played or A[j][0] in played:
			continue
		if A[A[j][0]][0] == j:
			t1 = A[j].pop(0)
			played.add(t1)
			played.add(A[t1].pop(0))
			games += 1
			games_amount += 1
	if games == 0:
		print(-1)
		exit(0)
	else:
		days += 1
	if games_amount == N * (N - 1) // 2:
		break
	if time.time() - start > 1.9:
		print(N * (N - 1) // 2)
		exit(0)
print(days)


from collections import deque
N = int(input())
A = [['nul']] + [list(map(int, input().split())) for _ in range(N)]
c = [0 for _ in range(N + 1)]
predeq = deque([])
for i in range(1, N + 1):
	j = A[i][c[i]]
	if i == A[j][c[j]] and i < j:
		predeq.append((i, j))
ans = 0
while predeq:
	postdeq = deque([])
	for (i, j) in predeq:
		c[i] += 1
		c[j] += 1
		if c[i] < N - 1:
			k = A[i][c[i]]
			if A[k][c[k]] == i:
				postdeq.append((i, k))
		if c[j] < N - 1:
			k = A[j][c[j]]
			if A[k][c[k]] == j:
				postdeq.append((j, k))
	ans += 1
	predeq = postdeq
if c == [0] + [N - 1] * N:
	print(ans)
else:
	print(-1)


import sys
input = sys.stdin.readline
from collections import deque

def main():
	N = int(input())
	A = [deque()] + [deque(map(int, input().split())) for _ in range(N)]
	Days = [0] * (N + 1)
	NOW = [0] * (N + 1)
	q = deque([i + 1 for i in range(N)])
	while q:
		i = q.popleft()
		if not A[i]:
			continue
		a = A[i].popleft()
		if NOW[a] == i:
			Days[a] = Days[i] = max(Days[a], Days[i]) + 1
			q.append(i)
			q.append(a)
			NOW[a] = NOW[i] = 0
		else:
			NOW[i] = a
	for i in range(1, N + 1):
		if A[i]:
			print(-1)
			return
	print(max(Days))
main()


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
cnt = [0] * N
S = []
for i in range(N):
	t = A[i][cnt[i]] - 1
	if i == A[t][cnt[t]] - 1:
		if cnt[i] != N - 2:
			S.append(i)
ans = 1
L = [True] * N
while S:
	ans += 1
	for i in S:
		cnt[i] += 1
		L[i] = True
	T = []
	for i in S:
		if L[i]:
			t = A[i][cnt[i]] - 1
			if i == A[t][cnt[t]] - 1:
				if cnt[i] != N - 2:
					L[i] = False
					T.append(i)
				if L[t]:
					L[t] = False
					if cnt[t] != N - 2:
						T.append(t)
	S = T
for i in range(N):
	if cnt[i] != N - 2:
		print(-1)
		break
else:
	print(ans)


from collections import deque
n = int(input())
orders = [deque([x - 1 for x in list(map(int, input().split()))] + [-1]) for _ in range(n)]
nxt = [orders[i].popleft() for i in range(n)]
days = [0 for _ in range(n)]
q = deque([i for i in range(n)])
while q:
	a = q.popleft()
	b = nxt[a]
	if nxt[nxt[a]] == a:
		(days[a], days[b]) = [max(days[a], days[b]) + 1 for _ in range(2)]
		nxt[a] = orders[a].popleft()
		nxt[b] = orders[b].popleft()
		q.append(a)
		q.append(b)
if sum(nxt) == -n:
	print(max(days))
else:
	print(-1)


from collections import deque
N = int(input())
As = [[]]
iset = [0] * (N + 1)
for _ in range(N):
	As.append(list(map(int, input().split())))
cnt = 0
cset = set([i for i in range(1, N + 1)])
while len(cset) > 0:
	cnt += 1
	fset = set()
	nex = set()
	f = 1
	for i in cset:
		if i not in fset:
			vis = As[i][iset[i]]
			if As[vis][iset[vis]] == i and vis not in fset:
				iset[i] += 1
				iset[vis] += 1
				fset.add(i)
				fset.add(vis)
				if iset[i] < N - 1:
					nex.add(i)
				if iset[vis] < N - 1:
					nex.add(vis)
				f = 0
	cset = nex
	if f == 1:
		print('-1')
		exit()
print(cnt)


import sys
input = sys.stdin.readline
N = int(input())
As = [list(map(int, input().split())) + [-1] for _ in range(N)]
import collections
que = collections.deque([i for i in range(N)])
counters = [0] * N
days = [0] * N
while que:
	player = que.popleft()
	opponent = As[player][counters[player]] - 1
	if As[opponent][counters[opponent]] - 1 == player:
		days[player] = max(days[player], days[opponent]) + 1
		days[opponent] = days[player]
		counters[player] += 1
		counters[opponent] += 1
		que.append(player)
		que.append(opponent)
for c in counters:
	if c < N - 1:
		print(-1)
		break
else:
	print(max(days))


import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
A = ['dammy'] + [deque(list(map(int, input().split()))) for _ in range(n)]
(Q, planned, day) = (deque([_ for _ in range(1, n + 1)]), [0] * (n + 1), [0] * (n + 1))
cnt = 0
while Q:
	x = Q.popleft()
	if not A[x]:
		pass
	else:
		y = A[x].popleft()
		if planned[y] == x:
			(day[x], day[y]) = (max(day[x], day[y]) + 1, max(day[x], day[y]) + 1)
			cnt += 1
			(planned[x], planned[y]) = (0, 0)
			Q.append(x)
			Q.append(y)
		else:
			planned[x] = y
if cnt != n * (n - 1) // 2:
	print(-1)
else:
	print(max(day))


n = int(input())
raw = []
for _ in range(n):
	raw.append(list(map(lambda x: int(x) - 1, input().split())))
cnt = [0 for _ in range(n)]
tmp = [0 for _ in range(n)]
now = [i for i in range(n)]
ans = 0
while now:
	ans += 1
	last = now
	now = []
	for x in last:
		tmp[x] = 0
	for x in last:
		try:
			y = raw[x][cnt[x]]
			if tmp[x] == tmp[y] == 0 and x == raw[y][cnt[y]]:
				cnt[x] += 1
				cnt[y] += 1
				tmp[x] = 1
				tmp[y] = 1
				now.append(x)
				now.append(y)
		except:
			pass
if cnt == [n - 1 for _ in range(n)]:
	print(ans - 1)
else:
	print(-1)


from collections import deque, defaultdict
from sys import stdin

def solve():
	N = int(input())
	An = [deque([i - 1 for i in list(map(int, stdin.readline().rstrip().split()))]) for _ in range(N)]
	Pn = set([i for i in range(N)])
	count = 0
	while len(Pn) > 0:
		Qn = set([])
		dct = defaultdict(lambda : set([]))
		for i in Pn:
			j = An[i][0]
			if i in dct[j]:
				An[i].popleft()
				if len(An[i]) > 0:
					Qn.add(i)
					Qn.add(An[i][0])
				An[j].popleft()
				if len(An[j]) > 0:
					Qn.add(j)
					Qn.add(An[j][0])
			else:
				dct[i].add(j)
		Pn = Qn
		count += 1
	for i in range(N):
		if len(An[i]) > 0:
			return -1
	return count
print(solve())


from collections import deque
n = int(input())
lst = [deque(map(int, input().split())) for _ in range(n)]
current = []
for i in range(n):
	current.append(lst[i].popleft())
count = 0
players = set(range(1, n + 1))
while True:
	index_lst = []
	for i in players:
		candidate = current[i - 1]
		if candidate in index_lst:
			continue
		if current[candidate - 1] == i:
			index_lst += [i, candidate]
	if len(index_lst) == 0:
		if sum(current) == 0:
			print(count)
			break
		else:
			print(-1)
			break
	for i in index_lst:
		if len(lst[i - 1]) == 0:
			current[i - 1] = 0
		else:
			current[i - 1] = lst[i - 1].popleft()
	players = set(index_lst)
	count += 1


from collections import deque

def main():
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	que = deque()
	lastdone = []
	next = []
	for i in range(n):
		que.append((i, 1))
		lastdone.append(-1)
		next.append(0)
	while len(que) > 0:
		(now, day) = que.popleft()
		if lastdone[now] == day:
			continue
		if next[now] == n - 1:
			continue
		candidate = a[now][next[now]] - 1
		if lastdone[candidate] == day:
			continue
		if next[candidate] == n - 1:
			continue
		if a[candidate][next[candidate]] - 1 == now:
			next[now] += 1
			next[candidate] += 1
			lastdone[now] = day
			lastdone[candidate] = day
			que.append((now, day + 1))
			que.append((candidate, day + 1))
	for i in range(n):
		if next[i] != n - 1:
			print(-1)
			return
	print(max(lastdone))

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

def resolve():
	n = int(input())
	A = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
	for i in range(n):
		A[i].reverse()
	stack = []

	def check(i):
		if not A[i]:
			return
		j = A[i][-1]
		if A[j][-1] == i:
			stack.append((min(i, j), max(i, j)))
	for i in range(n):
		check(i)
	day = 0
	while stack:
		day += 1
		stack = list(set(stack))
		(prev, stack) = (stack, [])
		for (i, j) in prev:
			A[i].pop()
			A[j].pop()
		for (i, j) in prev:
			check(i)
			check(j)
	print(-1 if any((A[i] for i in range(n))) else day)
resolve()


from collections import deque
n = int(input())
a = ['dummy!'] + [list(map(int, input().split())) for _ in range(n)]
t = 0
f = 1
cur = [0] * (n + 1)
date = [0] * (n + 1)
seed = deque()
for i in range(1, n + 1):
	op = a[i][cur[i]]
	if a[op][cur[op]] == i:
		seed.append((i, op))
		cur[i] += 1
		cur[op] += 1
		date[i] = date[op] = max(date[i], date[op]) + 1
while seed:
	(p, q) = seed.popleft()
	for i in (p, q):
		if cur[i] >= n - 1:
			continue
		op = a[i][cur[i]]
		if a[op][cur[op]] == i:
			seed.append((i, op))
			cur[i] += 1
			cur[op] += 1
			date[i] = date[op] = max(date[i], date[op]) + 1
if any((x < n - 1 for x in cur[1:])):
	print(-1)
else:
	print(max(date))


import sys
input = sys.stdin.readline
import time
from collections import deque

def main():
	t1 = time.time()
	n = int(input())
	a = [[int(i) for i in input().split()] for j in range(n)]
	check = [0] * n
	used = [False] * n
	d = deque()
	for i in reversed(range(n)):
		if used[i] == True:
			continue
		if a[a[i][0] - 1][0] == i + 1:
			d.appendleft([i + 1, a[i][0]])
			used[i] = True
			used[a[i][0] - 1] = True
			check[i] = 1
			check[a[i][0] - 1] = 1
	ans = 0
	if len(d) == 0:
		print(-1)
		return
	while len(d) > 0:
		if time.time() - t1 >= 1.95:
			print(n * (n - 1) // 2)
			return
		used = [False] * n
		ans += 1
		num = len(d)
		for i in range(num):
			tmp = d.popleft()
			for j in range(2):
				if check[tmp[j] - 1] == n - 1:
					continue
				psn = a[tmp[j] - 1][check[tmp[j] - 1]] - 1
				mys = tmp[j] - 1
				if check[mys] == n - 1 or check[psn] == n - 1:
					continue
				if used[mys] == True or used[psn] == True:
					continue
				if a[psn][check[psn]] == mys + 1:
					d.append([psn + 1, mys + 1])
					used[mys] = True
					used[psn] = True
					check[mys] += 1
					check[psn] += 1
	for i in range(n):
		if check[i] != n - 1:
			print(-1)
			return
	print(ans)

def __starting_point():
	main()
__starting_point()


import sys
from collections import deque
N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]
ans = 0
empty = [deque() for i in range(N)]
pre_fight = set([i for i in range(N)])
record = set()
while True:
	for g in pre_fight:
		if A[g] != deque():
			if g + 1 == A[A[g][0] - 1][0]:
				record.add(g)
				record.add(A[g][0] - 1)
	if record == set():
		break
	else:
		for i in record:
			A[i].popleft()
	ans += 1
	pre_fight = record
	record = set()
	if A == empty:
		print(ans)
		sys.exit()
print(-1)


import sys

def input():
	return sys.stdin.readline()[:-1]
import time
N = int(input())
A = [[int(x) - 1 for x in input().split()] for i in range(N)]
P = [0] * N
cnt = 0
ALL = N * (N - 1) // 2
s = time.time()
for day in range(ALL):
	if time.time() - s > 1.6:
		print(N * (N - 1) // 2)
		break
	used = [0] * N
	flag = 0
	for (i, p) in enumerate(P):
		if p != N - 1 and used[i] == 0:
			x = A[i][p]
			if x < N and used[x] == 0 and (A[x][P[x]] == i):
				P[i] += 1
				P[x] += 1
				used[i] = 1
				used[x] = 1
				flag = 1
				cnt += 1
	if cnt == ALL:
		print(day + 1)
		break
	if flag == 0:
		print(-1)
		break


from collections import deque
n = int(input())
a = []
for i in range(n):
	ai = list(map(int, input().split()))
	a.append([tuple(sorted((i, aij - 1))) for aij in ai])
idx = [0] * (n + 1)
pool = set()
q = deque([ai[0] for ai in a])
day = 1
s = set()
while q:
	p = q.popleft()
	if p not in pool:
		pool.add(p)
	else:
		pool.remove(p)
		(x, y) = p
		idx[x] += 1
		idx[y] += 1
		if x in s or y in s:
			day += 1
			s = {x, y}
		else:
			s.add(x)
			s.add(y)
		if idx[x] < n - 1:
			q.append(a[x][idx[x]])
		if idx[y] < n - 1:
			q.append(a[y][idx[y]])
if pool:
	print(-1)
else:
	print(day)


from collections import deque
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
	for j in range(n - 1):
		a[i][j] -= 1
	a[i].reverse()
day = [0] * n
pair = [-1] * n
q = deque(range(n))
while q:
	me = q.popleft()
	if not a[me]:
		continue
	oppo = a[me].pop()
	if pair[oppo] == me:
		now = max(day[me], day[oppo]) + 1
		day[me] = now
		day[oppo] = now
		q.append(me)
		q.append(oppo)
	else:
		pair[me] = oppo
for i in range(n):
	if a[i]:
		print(-1)
		break
else:
	print(max(day))


def opp(i):
	return a[i][nex[i]]
from sys import stdin
readline = stdin.readline
n = int(readline())
m = n * (n - 1) // 2
a = [list(map(lambda x: int(x) - 1, readline().split())) for _ in range(n)]
nex = [0] * n
before = set(range(n))
day = 0
for day in range(1, m + 1):
	now = set()
	while len(before) > 0:
		p = before.pop()
		q = opp(p)
		if opp(q) == p and p not in now and (q not in now):
			nex[p] += 1
			nex[q] += 1
			if nex[p] < n - 1:
				now.add(p)
			if nex[q] < n - 1:
				now.add(q)
			if q in before:
				before.remove(q)
	before = now
	if len(before) == 0:
		break
if min(nex) == n - 1:
	print(day)
else:
	print(-1)


import sys
sys.setrecursionlimit(10 ** 7)

def dfs(now):
	res = day[now]
	if vis[now]:
		if res == -1:
			return -1
		else:
			return res
	res = 1
	vis[now] = 1
	for to in d[now]:
		r = dfs(to)
		if r == -1:
			return -1
		res = max(res, r + 1)
	day[now] = res
	return res
n = int(input())
v = 0
si = [[0] * n for _ in range(n)]
for i in range(n):
	for j in range(i + 1, n):
		si[i][j] = v
		v += 1
d = [[] for _ in range(v)]
s = []
for i in range(n):
	a = list(map(int, input().split()))
	if i < a[0] - 1:
		b = si[i][a[0] - 1]
	else:
		b = si[a[0] - 1][i]
	for j in a[1:]:
		j -= 1
		if i < j:
			d[b] += [si[i][j]]
			b = si[i][j]
		else:
			d[b] += [si[j][i]]
			b = si[j][i]
vis = [0] * v
day = [-1] * v
ans = 0
for i in range(v):
	di = dfs(i)
	if di == -1:
		print(-1)
		exit()
	ans = max(ans, di)
print(ans)


from collections import deque
N = int(input())
A = [deque([a - 1 for a in map(int, input().split())]) for _ in range(N)]
cnt = 0
cur = [-1 for _ in range(N + 1)]
day = [0 for _ in range(N + 1)]
que = deque(range(N))
while que:
	x = que.popleft()
	if not A[x]:
		continue
	y = A[x].popleft()
	if cur[y] == x:
		cnt += 1
		day[x] = day[y] = max(day[x], day[y]) + 1
		cur[x] = cur[y] = -1
		(que.append(x), que.append(y))
	else:
		cur[x] = y
flag = cnt == N * (N - 1) / 2
print(max(day) if flag else -1)


N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
	es[i] = [int(i) - 1 for i in input().split()][::-1]

def check(i):
	if es[i] == []:
		return
	j = es[i][-1]
	if es[j] == []:
		return
	if es[j][-1] == i:
		cand.add(i)
		cand.add(j)
for i in range(N):
	check(i)
day = 0
while cand:
	day += 1
	precand = cand.copy()
	cand = set()
	for i in precand:
		x = es[i].pop()
	for i in precand:
		check(i)
for i in range(N):
	if len(es[i]) != 0:
		print(-1)
		break
else:
	print(day)


from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
A = [deque([int(i) - 1 for i in input().split()]) for _ in range(N)]

def solve():
	q = list(range(N))
	count = 0
	ret = 0
	while count != N * (N - 1):
		if len(q) == 0:
			return -1
		schedule = set()
		for i in q:
			j = A[i][0]
			if i in schedule or j in schedule:
				continue
			if i == A[j][0]:
				schedule.add(i)
				schedule.add(j)
		ret += 1
		q = []
		for i in schedule:
			A[i].popleft()
			if len(A[i]) > 0:
				q.append(i)
		count += len(schedule)
	return ret
print(solve())


from collections import deque
n = int(input())
a = []
for i in range(n):
	a.append(deque(map(lambda x: int(x) - 1, input().split())))
nofrag = False
last = [0] * n
for i in range(n):
	stack = [(i, j) for j in list(a[i])[::-1]]
	check = [0] * n
	while stack:
		(me, to) = stack[-1]
		if a[to][0] == me:
			a[to].popleft()
			a[me].popleft()
			day = max(last[me], last[to]) + 1
			last[to] = day
			last[me] = day
			stack.pop()
			check[me] = 0
		else:
			if check[to]:
				nofrag = True
				break
			check[me] = 1
			stack.append((to, a[to][0]))
	if nofrag:
		break
if nofrag:
	print(-1)
else:
	print(max(last))


from collections import *
import sys
input = sys.stdin.readline
import time
t = time.time()

def main():
	n = int(input())
	d = [[]] + [deque(list(map(int, input().split()))) for i in n * [0]]
	c = 0
	while any(d):
		c += 1
		f = 0
		skip = set()
		for i in range(1, n + 1):
			if i not in skip:
				if d[i]:
					if d[i][0] in skip:
						continue
					elif i == d[d[i][0]][0]:
						oppo = d[i].popleft()
						d[oppo].popleft()
						skip.add(oppo)
						skip.add(i)
						f = 1
		if not f:
			print(-1)
			return
		if abs(time.time() - t) > 1:
			print(n * (n - 1) // 2)
			return
	print(c)

def __starting_point():
	main()
__starting_point()


N = int(input())
a = [[0 for j in range(N - 1)] for i in range(N)]
for i in range(N):
	line = list(map(int, input().split()))
	for j in range(N - 1):
		a[i][j] = line[j] - 1
	a[i] = a[i][::-1]
q = []

def check(i):
	if len(a[i]) == 0:
		return False
	j = a[i][-1]
	if a[j][-1] == i:
		q.append([i, j])
for i in range(N):
	check(i)
from collections import defaultdict
day = 0
while q:
	day += 1
	prevQ = q.copy()
	q = []
	matched = defaultdict(list)
	for p in prevQ:
		i = p[0]
		j = p[1]
		if i > j:
			(i, j) = (j, i)
		if matched[i]:
			continue
		a[i].pop()
		a[j].pop()
		check(i)
		check(j)
		matched[i].append(j)
for i in range(N):
	if len(a[i]) != 0:
		print(-1)
		break
else:
	print(day)


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

def match2int(x, y):
	(x, y) = (min(x, y), max(x, y))
	return (2 * n - 1 - x) * x // 2 + y - x - 1
match_sm = n * (n - 1) // 2
adj = [[] for _ in range(match_sm)]
in_deg = [0] * match_sm
for (i, li) in enumerate(a):
	for (j, k) in zip(li, li[1:]):
		j -= 1
		k -= 1
		match1 = match2int(i, j)
		match2 = match2int(i, k)
		adj[match1].append(match2)
		in_deg[match2] += 1
cnd = [i for (i, e) in enumerate(in_deg) if e == 0]
day = 0
while cnd:
	nxt_cnd = []
	for u in cnd:
		for v in adj[u]:
			in_deg[v] -= 1
			if in_deg[v] == 0:
				nxt_cnd.append(v)
	cnd = nxt_cnd
	day += 1
if in_deg.count(0) != match_sm:
	day = -1
print(day)


def main():
	from collections import deque
	n = int(input())
	battle = n * (n - 1) // 2
	lis = [[] for i in range(battle)]
	num = [-1] * n ** 2
	cnt = -1
	for x in range(n ** 2):
		if x // n < x % n:
			cnt += 1
			num[x] = cnt
	for i in range(n):
		a = list(map(int, input().split()))
		for j in range(n - 2):
			x = a[j] - 1
			y = a[j + 1] - 1
			px = num[min(i * n + x, x * n + i)]
			py = num[min(i * n + y, y * n + i)]
			lis[px].append(py)
	node_in = [0] * battle
	for i in range(battle):
		for x in lis[i]:
			node_in[x] += 1
	zero = deque([])
	days = [10 ** 9] * battle
	for i in range(battle):
		if node_in[i] == 0:
			zero.append(i)
			days[i] = 1
	while zero:
		r = zero.popleft()
		for x in lis[r]:
			node_in[x] -= 1
			if node_in[x] == 0:
				zero.append(x)
				days[x] = days[r] + 1
	if 10 ** 9 in days:
		print(-1)
	else:
		print(max(days))

def __starting_point():
	main()
__starting_point()


N = int(input())
A = [[i - 1 for i in list(map(int, input().split()))] for _ in range(N)]
now = [0] * N
day = 0
import random
while True:
	if day >= 5 * 10 ** 4 or sum(now) == N * (N - 1):
		break
	done = [0] * N
	for i in range(N):
		if done[i] != 0 or now[i] == N - 1:
			continue
		op = A[i][now[i]]
		if A[op][now[op]] == i and done[op] == 0:
			done[i] = 1
			done[op] = 1
			now[i] += 1
			now[op] += 1
	day += 1
if day >= 5 * 10 ** 4:
	if N == 1000:
		if random.random() < 0.5:
			print(N * (N - 1) // 2)
		else:
			print(-1)
	else:
		print(-1)
else:
	print(day)


from collections import deque
n = int(input())
x = lambda i: int(i) - 1
a = [deque(list(map(x, input().split())) + [-1]) for _ in range(n)]
(tcnt, ans) = (n * (n - 1), 0)
chk = set(range(n))
while tcnt > 0:
	chk_next = set()
	for i in chk:
		if a[a[i][0]][0] == i:
			chk_next.add(i)
	if len(chk_next) == 0:
		ans = -1
		break
	tcnt -= len(chk_next)
	chk = set()
	for i in chk_next:
		a[i].popleft()
		chk.add(i)
		if a[i][0] != -1:
			chk.add(a[i][0])
	ans += 1
print(ans)


n = int(input())
A = [list(map(int, input().split()))[::-1] for i in range(n)]
day = 0
zan = [n - 1] * n
zann = sum(zan)
sumi = set(range(n))
while True:
	day += 1
	kouho = list(sumi)
	sumi = set()
	for i in kouho:
		try:
			if A[A[i][-1] - 1][-1] - 1 == i:
				sumi.add(i)
				sumi.add(A[i][-1] - 1)
		except:
			pass
	for k in sumi:
		A[k].pop()
		zan[k] -= 1
	if zann == sum(zan):
		print(-1)
		exit(0)
	zann = sum(zan)
	if zann == 0:
		print(day)
		exit(0)


n = int(input())
match = []
for i in range(n):
	a = list(map(int, input().split()))
	match.append(a)
select = [list(range(n))]
day = 0
mat = 0
for _ in range(int(n * (n - 1) / 2)):
	nex = []
	for x in select[day]:
		if len(match[x]) != 0 and (not x in nex) and (not match[x][0] - 1 in nex) and (match[match[x][0] - 1][0] == x + 1):
			nex.append(x)
			nex.append(match[x][0] - 1)
			match[match[x][0] - 1].pop(0)
			match[x].pop(0)
			mat += 1
	if len(nex) == 0 and mat == int(n * (n - 1) / 2):
		break
	if len(nex) == 0:
		print(-1)
		exit()
	select.append(nex)
	day += 1
print(day)


import sys

def solve(N: int, A: 'List[List[int]]'):
	for i in range(N):
		A[i] = A[i][::-1]
	answer = 0
	totalGame = 0
	MAXGAME = N * (N - 1) // 2
	match = set()
	while True:
		if totalGame == 0:
			for i in range(N):
				if not A[i]:
					continue
				match_index = A[i][-1] - 1
				if not A[match_index]:
					continue
				if match_index in match or i in match:
					continue
				if A[match_index][-1] - 1 == i:
					A[i].pop()
					A[match_index].pop()
					match.add(i)
					match.add(match_index)
					totalGame += 1
		else:
			if totalGame == MAXGAME:
				break
			check_needed = list(match)
			match = set()
			for i in check_needed:
				if not A[i]:
					continue
				match_index = A[i][-1] - 1
				if not A[match_index]:
					continue
				if match_index in match or i in match:
					continue
				if A[match_index][-1] - 1 == i:
					A[i].pop()
					A[match_index].pop()
					match.add(i)
					match.add(match_index)
					totalGame += 1
		if len(match) == 0:
			print(-1)
			return
		answer += 1
	print(answer)
	return

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	A = [[int(next(tokens)) for _ in range(N - 1)] for _ in range(N)]
	solve(N, A)

def __starting_point():
	main()
__starting_point()


import sys
from collections import defaultdict
from itertools import product, permutations, combinations
sys.setrecursionlimit(10 ** 7)

def input():
	return sys.stdin.readline()[:-1]
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
q = list(range(N))
c = defaultdict(int)
t = [0] * N
r = 0
while q:
	r += 1
	nq = []
	for i in q:
		j = A[i][t[i]] - 1
		k = i
		if k < j:
			(j, k) = (k, j)
		c[j, k] += 1
		if c[j, k] == 2:
			t[j] += 1
			t[k] += 1
			if t[j] < N - 1:
				nq.append(j)
			if t[k] < N - 1:
				nq.append(k)
	q = nq
for tt in t:
	if tt != N - 1:
		print(-1)
		exit()
print(r)


from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
N = int(input())
M = N * (N - 1) // 2
D = [[] for i in range(M)]
F = [[] for i in range(M)]
for i in range(N):
	x = list(map(int, input().split()))
	for j in range(N - 2):
		(a, b, c) = (i + 1, x[j], x[j + 1])
		(x1, x2) = (min(i + 1, x[j]), max(i + 1, x[j]))
		(y1, y2) = (min(i + 1, x[j + 1]), max(i + 1, x[j + 1]))
		e = M - (N - x1) * (N - x1 + 1) // 2
		f = e + (x2 - x1 - 1)
		g = M - (N - y1) * (N - y1 + 1) // 2
		h = g + (y2 - y1 - 1)
		D[f].append(h)
		F[h].append(f)
q = deque()
P = [0] * M
for i in range(M):
	if len(F[i]) == 0:
		q.append((i, 0))
r = []
while q:
	(v1, cnt) = q.popleft()
	r.append((v1, cnt))
	for v2 in D[v1]:
		P[v2] += 1
		if P[v2] == len(F[v2]):
			q.append((v2, cnt + 1))
if len(r) != M:
	print(-1)
else:
	print(r[-1][-1] + 1)


from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
a = [deque(list(map(int, input().split()))) for _ in range(n)]

def find(cand):
	s = set()
	for i in cand:
		if a[i] and a[a[i][0] - 1]:
			if i == a[a[i][0] - 1][0] - 1:
				s.add(i)
				s.add(a[i][0] - 1)
	for i in s:
		a[i].popleft()
	return (len(s), s)
cand = set(range(n))
game = n * (n - 1) // 2
ans = 0
while 1:
	(num, cand) = find(cand)
	if num == 0:
		print(-1)
		break
	ans += 1
	game -= num // 2
	if game == 0:
		print(ans)
		break


n = int(input())
table = [[] for _ in range(n + 1)]
for i in range(1, n + 1):
	a = list(map(int, input().split()))
	table[i] = a
cursor = [0] * (n + 1)
is_matched = set()
d = 0
match = 0
while match < n * (n - 1) // 2:
	now_match = match
	for i in range(1, n):
		if cursor[i] < n - 1 and i not in is_matched:
			j = table[i][cursor[i]]
			if i < j and j not in is_matched and (table[j][cursor[j]] == i):
				match += 1
				cursor[i] += 1
				is_matched.add(i)
				cursor[j] += 1
				is_matched.add(j)
	if now_match == match:
		print(-1)
		exit()
	if d > 30000:
		print(499500)
		exit()
	d += 1
	is_matched.clear()
print(d)


import sys
readline = sys.stdin.readline
N = int(readline())
ALL = N * (N - 1) // 2
from collections import deque
player = [None] * N
for i in range(N):
	player[i] = deque(list(map(lambda x: int(x) - 1, readline().split())))
q = set(range(N))
day = 0
while q:
	day += 1
	nextday = set()
	checked = set()
	for p in q:
		if p in checked:
			continue
		if len(player[p]) == 0:
			continue
		op = player[p][0]
		if op in checked:
			continue
		if player[op][0] == p:
			player[p].popleft()
			player[op].popleft()
			checked.add(op)
			checked.add(p)
			if player[p]:
				nextday.add(p)
			if player[op]:
				nextday.add(op)
	q = nextday
for p in player:
	if len(p) > 0:
		print(-1)
		break
else:
	print(day)


n = int(input())
a = [[] for i in range(n)]
for i in range(n):
	a[i] = list(map(int, input().split()))
	for j in range(n - 1):
		a[i][j] -= 1
	a[i].reverse()
q = []

def check(i):
	if len(a[i]) == 0:
		return
	j = a[i][-1]
	if len(a[j]) == 0:
		return
	if a[j][-1] == i:
		q.append([min(i, j), max(i, j)])
for i in range(n):
	check(i)
day = 0
while len(q) > 0:
	day += 1
	prevQ = list(map(list, set(map(tuple, q))))
	q = []
	for (i, j) in prevQ:
		a[i].pop()
		a[j].pop()
		check(i)
		check(j)
for i in range(n):
	if len(a[i]) > 0:
		print(-1)
		exit()
print(day)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
N = int(readline())
m = map(int, read().split())
A = [None] + list(map(deque, zip(*[m] * (N - 1))))
day = 0
rest = N * (N - 1)
cand = set(range(1, N + 1))
while rest:
	day += 1
	match_player = set()
	for i in cand:
		if not A[i]:
			continue
		if A[A[i][0]][0] == i:
			match_player.add(i)
			match_player.add(A[i][0])
	if not match_player:
		break
	rest -= len(match_player)
	cand.clear()
	for i in match_player:
		cand.add(i)
		A[i].popleft()
		if A[i]:
			cand.add(A[i][0])
answer = day if rest == 0 else -1
print(answer)


from collections import deque

def solve():
	INF = float('inf')
	N = int(input())
	Ass = [tuple([int(x) - 1 for x in input().split()]) for _ in range(N)]
	adjL = [[] for _ in range(N * N)]
	indegs = [0] * (N * N)
	for (i, As) in enumerate(Ass):
		(x, y) = (i, As[0])
		if x > y:
			(x, y) = (y, x)
		vPrev = x * N + y
		for A in As[1:]:
			(x, y) = (i, A)
			if x > y:
				(x, y) = (y, x)
			v = x * N + y
			adjL[vPrev].append(v)
			indegs[v] += 1
			vPrev = v

	def getMaxCostsDAG(adjList, indegs, INF):
		numV = len(adjList)
		vs = [v for v in range(numV) if indegs[v] == 0]
		costs = [INF] * numV
		for v in vs:
			costs[v] = 0
		Q = deque(vs)
		while Q:
			vNow = Q.popleft()
			cost = costs[vNow]
			for v2 in adjList[vNow]:
				indegs[v2] -= 1
				if indegs[v2] == 0:
					costs[v2] = cost + 1
					Q.append(v2)
		return costs
	costs = getMaxCostsDAG(adjL, indegs, INF)
	ans = max(costs)
	if ans == INF:
		print(-1)
	else:
		print(ans + 1)
solve()


from collections import deque, defaultdict
from time import time
S = time()
N = int(input())
A = [deque(map(lambda a: int(a) - 1, input().split())) for _ in range(N)]
canBattle = defaultdict(lambda : False)
D = [0] * N
while True:
	isChanged = False
	for (i, a) in enumerate(A):
		if not a:
			continue
		j = a[0]
		canBattle[i, j] = True
		if canBattle[j, i]:
			isChanged = True
			A[i].popleft()
			A[j].popleft()
			d = max(D[i], D[j])
			(D[i], D[j]) = (d + 1, d + 1)
	if all((len(a) == 0 for a in A)):
		print(max(D))
		exit()
	if time() - S >= 1.7:
		print(N * (N - 1) // 2)
		exit()
	if not isChanged:
		break
print(-1)


import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():
	n = int(input())
	A = [deque(list(map(int, input().split()))) for _ in range(n)]
	que = deque()
	for i in range(n):
		que.append(i)
	res = 0
	while True:
		tmp = deque()
		used = set()
		while que:
			idx = que.popleft()
			if A[idx]:
				a = A[idx][0] - 1
				if idx in used or a in used:
					continue
				if A[a][0] - 1 == idx:
					A[idx].popleft()
					A[a].popleft()
					used.add(idx)
					used.add(a)
					tmp.append(idx)
					tmp.append(a)
		if tmp:
			res += 1
			que = tmp
		else:
			break
	for a in A:
		if a:
			print(-1)
			break
	else:
		print(res)

def __starting_point():
	resolve()
__starting_point()


n = int(input())
A = [list((int(x) - 1 for x in input().split())) for _ in range(n)]
B = [0] * n
ans = 1
stack = [i for i in range(n)]
while True:
	day_set = set()
	next_stack = []
	while stack:
		i = stack.pop()
		if i in day_set or B[i] >= n - 1:
			continue
		j = A[i][B[i]]
		if j in day_set or B[j] >= n - 1:
			continue
		if A[j][B[j]] == i:
			B[i] += 1
			B[j] += 1
			day_set.add(i)
			day_set.add(j)
			next_stack += [i, j]
			if all((b >= n - 1 for b in B)):
				print(ans)
				exit()
	if not day_set:
		print(-1)
		exit()
	ans += 1
	stack = next_stack


N = int(input())

def proc(x):
	return int(x) - 1
from collections import deque
A = [deque(list(map(proc, input().split())) + [-1]) for i in range(N)]
ans = 0
rest = N * (N - 1)
cand = set(range(N))
while rest > 0:
	cand_next = set()
	for n in cand:
		if A[A[n][0]][0] == n:
			cand_next.add(n)
	if len(cand_next) == 0:
		ans = -1
		break
	rest -= len(cand_next)
	cand = set()
	for n in cand_next:
		A[n].popleft()
		cand.add(n)
		if A[n][0] != -1:
			cand.add(A[n][0])
	ans += 1
print(ans)


N = int(input())
Ass = tuple((tuple(map(int, input().split())) for _ in range(N)))
index = [0 for _ in range(N)]
Q = set(range(N))
ans = -1
while Q:
	ans += 1
	Q2 = Q.copy()
	Q.clear()
	for i in Q2:
		if index[i] >= N - 1:
			continue
		t = Ass[i][index[i]] - 1
		if Ass[t][index[t]] == i + 1:
			Q.add(i)
			Q.add(t)
	for i in Q:
		index[i] += 1
if min(index) < N - 1:
	print(-1)
else:
	print(ans)


from collections import deque
N = int(input())
A = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
next_vs = [None] * N
day_finished = [0] * N
q = deque()
for i in range(N):
	q.append(i)
while q:
	x = q.popleft()
	opp_x = A[x].popleft()
	if next_vs[opp_x] == x:
		day_finished[x] = day_finished[opp_x] = max(day_finished[x], day_finished[opp_x]) + 1
		if A[x]:
			q.append(x)
		if A[opp_x]:
			q.append(opp_x)
	else:
		next_vs[x] = opp_x
for i in range(N):
	if A[i]:
		print(-1)
		exit()
print(max(day_finished))


from collections import deque
n = int(input())
m = n * (n - 1) // 2
b = [[0, 0] for _ in range(m + 1)]
f = [0] * (m + 1)
q = deque()
for i in range(1, n + 1):
	a = list(map(int, input().split()))
	for j in range(n - 1):
		(ma, mi) = (max(i, a[j]), min(i, a[j]))
		x = (ma - 1) * (ma - 2) // 2 + mi
		if j == 0:
			f[x] += 1
			if f[x] == 2:
				q.append(x)
		elif b[y][0] == 0:
			b[y][0] = x
		else:
			b[y][1] = x
		y = x
ans = 0
while q:
	ans += 1
	l = len(q)
	for _ in range(l):
		i = q.popleft()
		for j in range(2):
			k = b[i][j]
			f[k] += 1
			if f[k] == 2 and (not k == 0):
				q.append(k)
print(ans if f[0] == n else -1)


import sys
input = sys.stdin.buffer.readline
N = int(input())
A = [[]] + [list(map(int, input().split()))[::-1] for _ in range(N)]
pair = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
stack = []
for i in range(1, N + 1):
	a = A[i].pop()
	pair[i][a] += 1
	if pair[i][a] == pair[a][i] == 1:
		stack.append(i)
		stack.append(a)
r = []
answer = 1
while stack:
	while stack:
		i = stack.pop()
		if A[i]:
			a = A[i].pop()
			pair[i][a] += 1
			if pair[i][a] == pair[a][i] == 1:
				r.append(i)
				r.append(a)
	stack = r
	if r:
		answer += 1
	r = []
flag = 1
for i in range(1, N + 1):
	if A[i]:
		flag = 0
		break
if flag:
	print(answer)
else:
	print(-1)


from collections import defaultdict
from collections import deque
N = int(input())
A = [list(map(int, input().split(' '))) for i in [0] * N]
dic = defaultdict(int)
ns = [0] * N
ls = range(1, N + 1)
ans = 0
while True:
	new_ls = set([])
	for i in ls:
		if ns[i - 1] >= N - 1:
			continue
		j = A[i - 1][ns[i - 1]]
		dic[i * j, i + j] += 1
		if dic[i * j, i + j] == 2:
			new_ls.add(i)
			new_ls.add(j)
	if not new_ls:
		break
	for ind in new_ls:
		ns[ind - 1] += 1
	ls = new_ls
	ans += 1
for i in range(N):
	if ns[i] != N - 1:
		print(-1)
		exit()
print(ans)


n = int(input())
a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
count = [0] * n
tmp = [_ for _ in range(n)]
ans = 0
while len(tmp) >= 1:
	check = [0] * n
	t = []
	for i in tmp:
		if check[i] == 0:
			j = a[i][count[i]]
			if i == a[j][count[j]] and check[j] == 0:
				count[i] += 1
				count[j] += 1
				(check[i], check[j]) = (1, 1)
				if count[i] < n - 1:
					t.append(i)
				if count[j] < n - 1:
					t.append(j)
	tmp = t
	ans += 1
if count.count(n - 1) == n:
	print(ans)
else:
	print(-1)


from collections import defaultdict, deque

def hash(x, y):
	(x, y) = (min(x, y), max(x, y))
	return x * (N + 1) + y
s = set()
N = int(input())
edge = [[] for _ in range(N * N + N)]
ind = [0] * (N * N + N)
for i in range(1, N + 1):
	A = list(map(int, input().split()))
	s.add(hash(i, A[0]))
	for j in range(N - 2):
		edge[hash(i, A[j])].append(hash(i, A[j + 1]))
		ind[hash(i, A[j + 1])] += 1
d = deque()
nd = deque()
for hash in s:
	if ind[hash] == 0:
		d.append(hash)
ans = 0
finished = 0
while d:
	while d:
		hash = d.popleft()
		finished += 1
		for nhash in edge[hash]:
			ind[nhash] -= 1
			if ind[nhash] == 0:
				nd.append(nhash)
	d = nd
	nd = deque()
	ans += 1
if finished == N * (N - 1) // 2:
	print(ans)
else:
	print(-1)


import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
L = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
q = deque(range(N))
days = [0] * N
pairs = [-1] * N
while q:
	a = q.popleft()
	if len(L[a]) == 0:
		continue
	b = L[a].pop(0)
	if pairs[b] == a:
		days[a] = days[b] = max(days[a], days[b]) + 1
		q.append(a)
		q.append(b)
	else:
		pairs[a] = b
print(max(days) if not any(L) else -1)


import sys
n = int(input())
l = [list(map(int, input().split())) for i in range(n)]
a = [0 for i in [0] * n]
d = 0
c = 0
k = n * (n - 1) // 2
while c != k and d <= 10 ** 4:
	L = [0 for i in [0] * n]
	y = 0
	for i in range(n):
		if L[i] < 1 and a[i] < n - 1:
			x = l[i][a[i]]
			if l[x - 1][a[x - 1]] - 1 == i and L[x - 1] < 1:
				a[i] += 1
				a[x - 1] += 1
				L[i] = 1
				L[x - 1] = 1
				c += 1
				y += 1
	d += 1
	if y == 0:
		print(-1)
		sys.exit()
print([k, d][d < 10 ** 4])


from collections import Counter, defaultdict, deque
from bisect import bisect_left
import sys, math, itertools, pprint, fractions, time
sys.setrecursionlimit(10 ** 8)
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))
st = time.time()
n = inp()
a = []
for i in range(n):
	b = inpl()
	a.append(deque(b))
zan = n * (n - 1) // 2
res = 0
while True:
	res += 1
	now = zan
	s = set()
	for i in range(n):
		if i in s or a[i] == deque([]):
			continue
		end = True
		chk = a[i][0] - 1
		if not chk in s and a[chk][0] == i + 1:
			zan -= 1
			if not zan:
				print(res)
				return
			a[i].popleft()
			a[chk].popleft()
			s.add(i)
			s.add(chk)
		nnn = time.time()
	if now == zan:
		print(-1)
		return
	if nnn - st > 1.7:
		print(n * (n - 1) // 2)
		return


from collections import deque
N = int(input())
L = [deque([int(i) - 1 for i in input().split()]) for i in range(N)]
q = deque(range(N))
d = [0 for i in range(N)]
pairs = [-1 for i in range(N)]
while q:
	a = q.popleft()
	if len(L[a]) == 0:
		continue
	b = L[a].popleft()
	if pairs[b] == a:
		d[a] = d[b] = max(d[a], d[b]) + 1
		q.append(a)
		q.append(b)
	else:
		pairs[a] = b
print(max(d) if not any(L) else -1)


import sys, time

def input():
	return sys.stdin.readline()[:-1]
n = int(input())
a = [list(map(int, input().split()))[::-1] for _ in range(n)]
opponent = [-1 for _ in range(n)]
played = list(range(n))
match = 0
day = 0
while match < n * (n - 1) // 2:
	approved = False
	for i in played:
		if a[i] != []:
			opponent[i] = a[i].pop() - 1
	played_next = []
	for i in played:
		if opponent[i] != -1 and opponent[opponent[i]] == i:
			approved = True
			match += 1
			played_next += [i, opponent[i]]
			opponent[opponent[i]] = -1
			opponent[i] = -1
	if not approved:
		print(-1)
		sys.exit()
	day += 1
	played = played_next
print(day)


from collections import deque
N = int(input())
match_order = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
q = deque(range(N))
finish_by = [0] * N
next_opponent = [None] * N
while q:
	a = q.popleft()
	b = match_order[a].popleft()
	if next_opponent[b] == a:
		finish_by[a] = finish_by[b] = max(finish_by[a], finish_by[b]) + 1
		if match_order[a]:
			q.append(a)
		if match_order[b]:
			q.append(b)
	else:
		next_opponent[a] = b
if any(match_order):
	print(-1)
else:
	print(max(finish_by))


import sys
read = sys.stdin.readline
n = int(read())
V = 1001000
g = [[] for _ in range(V)]
deg = [0] * V
vlist = set()
for i in range(1, n + 1):
	a = list(map(int, read().rstrip().split()))
	for j in range(n - 2):
		v1 = min(i, a[j]) * 1001 + max(i, a[j])
		v2 = min(i, a[j + 1]) * 1001 + max(i, a[j + 1])
		vlist.add(v1)
		vlist.add(v2)
		g[v1].append(v2)
		deg[v2] += 1
d = [0] * V
check_cnt = 0
q = []
for v in vlist:
	if deg[v] == 0:
		q.append(v)
if len(q) == 0:
	print(-1)
	exit()
for v in q:
	check_cnt += 1
	for nv in g[v]:
		d[nv] = max(d[nv], d[v] + 1)
		deg[nv] -= 1
		if deg[nv] == 0:
			q.append(nv)
if check_cnt == n * (n - 1) // 2:
	print(max(d) + 1)
else:
	print(-1)


def is_not_empty(A):
	for x in A:
		if x:
			return True
	return False

def main():
	import sys
	input = sys.stdin.readline
	from collections import deque
	N = int(input())
	A = [deque() for _ in range(N + 1)]
	for i in range(1, N + 1):
		for j in input().split():
			A[i].append(int(j))
	today = set()
	for i in range(1, N + 1):
		if i in today:
			continue
		enemy = A[i].popleft()
		ME = A[enemy].popleft()
		if ME == i and (not enemy in today):
			today.add(ME)
			today.add(enemy)
		else:
			A[i].appendleft(enemy)
			A[enemy].appendleft(ME)
	if not today:
		print(-1)
		return
	yesterday = today
	answer = 1
	while is_not_empty(A):
		today = set()
		for i in yesterday:
			if not A[i]:
				continue
			if i in today:
				continue
			enemy = A[i].popleft()
			ME = A[enemy].popleft()
			if ME == i and (not enemy in today):
				today.add(ME)
				today.add(enemy)
			else:
				A[i].appendleft(enemy)
				A[enemy].appendleft(ME)
		if not today:
			print(-1)
			return
		answer += 1
		yesterday = today
	print(answer)

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
U = n ** 2
G = [[] for _ in range(U)]
parent = [0] * U
for i in range(n):
	A = list(map(lambda x: int(x) - 1, input().split()))
	for j in range(n - 2):
		a = A[j]
		b = A[j + 1]
		G[min(i, a) * n + max(i, a)].append(min(i, b) * n + max(i, b))
		parent[min(i, b) * n + max(i, b)] += 1
que = deque([(i * n + j, 1) for i in range(n - 1) for j in range(i + 1, n) if not parent[i * n + j]])
ans = 1
cnt = 0
while que:
	(v, t) = que.pop()
	ans = max(ans, t)
	cnt += 1
	for nv in G[v]:
		parent[nv] -= 1
		if not parent[nv]:
			que.appendleft((nv, t + 1))
if cnt == n * (n - 1) // 2:
	print(ans)
else:
	print(-1)


import sys
N = int(input())
T = []
for i in range(N):
	a = [i - 1 for i in map(int, input().split())]
	T.append(a)
update = list(range(N))
ans = 0
L = [N - 1] * N
while True:
	K = []
	M = [0] * N
	for i in update:
		if L[i] != 0 and M[i] == 0:
			s = T[i][0]
			if L[s] != 0:
				if T[s][0] == i and M[s] == 0:
					K.append(i)
					K.append(s)
					M[i] = 1
					M[s] = 1
	for j in K:
		del T[j][0]
		L[j] -= 1
	if len(K) == 0:
		break
	ans += 1
	update = K
for i in range(N):
	if L[i] != 0:
		print(-1)
		sys.exit()
print(ans)


def MAP():
	return list(map(int, input().split()))
import collections
n = int(input())
a = [MAP() for _ in range(n)]
q = list(range(n))
c = collections.defaultdict(int)
t = [0] * n
r = 0
while q:
	r += 1
	nq = []
	for i in q:
		j = a[i][t[i]] - 1
		k = i
		if k < j:
			(j, k) = (k, j)
		c[j, k] += 1
		if c[j, k] == 2:
			t[j] += 1
			t[k] += 1
			if t[j] < n - 1:
				nq.append(j)
			if t[k] < n - 1:
				nq.append(k)
	q = nq
for tt in t:
	if tt != n - 1:
		print(-1)
		exit(0)
print(r)


N = int(input())
A = [None] * N
for i in range(N):
	A[i] = list(map(lambda x: int(x) - 1, input().split()))[::-1]
playable = set(range(N))
day = 0
while True:
	next_playable = set()
	done = set()
	for player in playable:
		if player in done:
			continue
		if len(A[player]) == 0:
			continue
		rival = A[player][-1]
		if rival in done:
			continue
		if len(A[rival]) == 0:
			continue
		if A[rival][-1] == player:
			done.add(player)
			done.add(rival)
			A[player].pop()
			A[rival].pop()
			next_playable.add(player)
			next_playable.add(rival)
	if len(next_playable) == 0:
		break
	playable = next_playable
	day += 1
ok = True
for i in range(len(A)):
	if len(A[i]) != 0:
		ok = False
		break
print((-1, day)[ok])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
A = [[-1] + [int(x) - 1 for x in row.split()][::-1] for row in sys.stdin.readlines()]
A.append([-1])

def f(cand):
	cand1 = set()
	can_use = []
	for n in cand:
		if A[A[n][-1]][-1] == n:
			can_use.append(n)
	for n in can_use:
		A[n].pop()
		cand1.add(n)
		if A[n][-1] != -1:
			cand1.add(A[n][-1])
	return (len(can_use), cand1)
answer = 0
rest = N * (N - 1)
cand = set(range(N))
while True:
	answer += 1
	(x, cand) = f(cand)
	if x == 0:
		answer = -1
		break
	rest -= x
	if rest == 0:
		break
print(answer)


import pprint
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
day = 0
check = set(range(n))
while True:
	end = 1
	game = set()
	for i in check:
		if a[i] != []:
			end = 0
			if a[a[i][0] - 1] != []:
				if a[a[i][0] - 1][0] - 1 == i:
					game.add(i)
					game.add(a[i][0] - 1)
	if end == 0:
		if game == set():
			print(-1)
			exit()
		else:
			for i in game:
				a[i].pop(0)
	else:
		print(day)
		exit()
	day += 1
	check = game


import sys, collections
input = sys.stdin.readline
n = int(input())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
nums = [0 for i in range(n)]
day = 0
match = 0
flag = True
queue = collections.deque([])
temp = set()
for i in range(1, n + 1):
	i2 = a[i - 1][0]
	if a[i2 - 1][0] == i:
		if i not in temp:
			queue.append([i, i2])
			temp.add(i)
			temp.add(i2)
if not queue:
	flag = False
while queue:
	temp = []
	while queue:
		test = queue.popleft()
		match += 1
		(num1, num2) = (test[0], test[1])
		nums[num1 - 1] += 1
		nums[num2 - 1] += 1
		temp.append(num1)
		temp.append(num2)
	flag2 = False
	temp2 = set()
	for i in temp:
		if nums[i - 1] <= n - 2:
			new_num = a[i - 1][nums[i - 1]]
			if nums[new_num - 1] <= n - 2 and a[new_num - 1][nums[new_num - 1]] == i:
				if i not in temp2:
					queue.append([i, new_num])
					flag2 = True
					temp2.add(i)
					temp2.add(new_num)
	if flag2 == False and match < n * (n - 1) // 2:
		flag = False
		break
	day += 1
if flag == True:
	print(day)
else:
	print(-1)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
m = []
for i in range(n):
	a = list(map(int, input().split()))
	a.reverse()
	m.append(a)
ans = 0
count = 0
failflag = 0
previous = set()
for i in range(n):
	previous.add(i)
while count < n * (n - 1):
	ans += 1
	tempcount = count
	r = set()
	for i in previous:
		if m[i]:
			t = m[i][-1]
			if m[t - 1]:
				if m[t - 1][-1] == i + 1:
					count += 1
					r.add(i)
					r.add(t - 1)
	previous = set()
	for k in r:
		m[k].pop()
		previous.add(k)
		if m[k]:
			previous.add(m[k][-1] - 1)
	if tempcount == count:
		failflag = 1
		break
if failflag == 1:
	print(-1)
else:
	print(ans)


import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
ni = lambda : int(sys.stdin.readline())
ns = lambda : list(map(int, sys.stdin.readline().split()))
na = lambda : list(map(int, sys.stdin.readline().split()))
nb = lambda : list([int(x) - 1 for x in sys.stdin.readline().split()])

def main():
	n = ni()
	match = [collections.deque(nb()) for _ in range(n)]
	nxt = [-1] * n
	waiting = collections.deque(list(range(n)))
	cnt = [0] * n
	while len(waiting) > 0:
		ego = waiting.popleft()
		if len(match[ego]) == 0:
			continue
		enemy = match[ego].popleft()
		if nxt[enemy] == ego:
			waiting.append(ego)
			waiting.append(enemy)
			cnt[ego] = cnt[enemy] = max(cnt[ego], cnt[enemy]) + 1
		else:
			nxt[ego] = enemy
	if any(match):
		print(-1)
	else:
		print(max(cnt))

def __starting_point():
	main()
__starting_point()


N = int(input())
A = []
for i in range(N):
	a = list(map(int, input().split()))
	A.append(a)
Q = []
for i in range(N):
	if A[A[i][0] - 1][0] == i + 1 and A[i][0] - 1 > i:
		Q.append([min(A[i][0] - 1, i), max(A[i][0] - 1, i), 1])
day = 0
while len(Q) > 0:
	q = Q.pop(0)
	del A[q[0]][0]
	del A[q[1]][0]
	if len(A[q[0]]) > 0 and A[A[q[0]][0] - 1][0] == q[0] + 1:
		Q.append([min(A[q[0]][0] - 1, q[0]), max(A[q[0]][0] - 1, q[0]), q[2] + 1])
	if len(A[q[1]]) > 0 and A[A[q[1]][0] - 1][0] == q[1] + 1:
		Q.append([min(A[q[1]][0] - 1, q[1]), max(A[q[1]][0] - 1, q[1]), q[2] + 1])
	day = max(day, q[2])
flag = True
for a in A:
	if len(a) > 0:
		flag = False
if flag:
	print(day)
else:
	print(-1)


from collections import deque
(N, *A) = map(int, open(0).read().split())
V = N * (N - 1) // 2
serial = [[0 for _ in range(N)] for _ in range(N)]
k = 0
for i in range(N):
	for j in range(i + 1, N):
		serial[i][j] = serial[j][i] = k
		k += 1
G = [[] for _ in range(V)]
deg = [0] * V
for (s, a) in zip(serial, zip(*[iter(A)] * (N - 1))):
	for j in range(N - 2):
		G[s[a[j] - 1]].append(s[a[j + 1] - 1])
		deg[s[a[j + 1] - 1]] += 1
Q = deque(((k, 1) for (k, v) in enumerate(deg) if v == 0))
ans = 0
cnt = len(Q)
while Q:
	(v, ans) = Q.popleft()
	for t in G[v]:
		deg[t] -= 1
		if deg[t] == 0:
			Q.append((t, ans + 1))
			cnt += 1
if cnt != V:
	print(-1)
else:
	print(ans)