Harryxun/stf_run huggingface dataset:
class UnionFind:
    def __init__(self, n):
        self.nodes=n
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n

    def find(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i]) # 経路圧縮
            return self.parents[i]

    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj
            else:
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
    def same(self, i, j):
        return self.find(i)==self.find(j)
    def get_parents(self):
        for n in range(self.nodes):
            selff.find(n)
        return self.parents

adj=[]
n, m = map(int,input().split())
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i==j:
            continue
        uf.unite(adj[j])
    if len(set(uf.get_parents()))!=1:
        ans+=1
print(ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.nodes = n
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n

    def find(self, i): # どの集合に属しているか（根ノードの番号）
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i]) # 経路圧縮
            return self.parents[i]

    def unite(self, i, j): # 二つの集合を併合
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj
            else:
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
    def same(self, i, j): # 同じ集合に属するかを判定
        return self.find(i)==self.find(j)

    def get_parents(self): # 根ノードの一覧を取得
        for n in range(self.nodes): # findで経路圧縮する
            self.find(n)
        return self.parents

adj = []
N, M = map(int,input().split())
for m in range(M):
    a,b = map(int,input().split())
    adj.append([a-1,b-1])

ans = 0
for i in range(M): # 取り除く辺番号
    uf = UnionFind(N)
    for j in range(M):
        if (i==j): # 辺を追加しない（取り除く）
            continue
        uf.unite(*adj[j])
    
    if len(set(uf.get_parents()))!=1: # 複数の集合にわかれているか確認
        ans += 1
print (ans)
#https://atcoder.jp/contests/dp/tasks/dp_b
#B - Frog 2

N=int(input())
H=list(map(int,input().strip().split(' ')))

dp=[0]*N

for i in range(1,N):
    MIN=10**9
    for j in range(1,K+1):
        if i-j<0:
            continue
        MIN=min(dp[i-j]+abs(H[i]-H[j]),MIN)
    dp[i]=MIN
print(dp[-1])        


### FIXED CODE ###

N,K=list(map(int,input().strip().split(" ")))
H=list(map(int,input().strip().split(" ")))
dp=[0]+[10**10]*(N-1)
for i in range(1,N):
    temp=0
    for j in range(i-K,i):
        if j>=0:
            dp[i]=min(dp[i],dp[j]+abs(H[i]-H[j]))
print(dp[-1])
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n,x=map(int, input().split())
    l=list(map(int,input().split()))
    if n==1:
        print(l[0]-x)
    else:
        l.append(x)
        l.sort()
        S=[]
        for i in range(n):
            S.append(l[i+1]-l[i])
        from functools import reduce
        from math import gcd
        print(reduce(gcd,S))
resolve()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n,x=map(int, input().split())
    l=list(map(int,input().split()))
    ll=[]
    for i in l:
        ll.append(abs(x-i))
    from functools import reduce
    from fractions import gcd
    print(reduce(gcd,ll))
resolve()
A=int(input())
B=int(input())
ans={1,2,3}-{A,B}
print(int(ans))


### FIXED CODE ###

A=int(input())
B=int(input())
ans={1,2,3}-{A,B}
print(ans.pop())
alice = input()
bob = input()
charlie = input()

for i in range(len(alice)):
  if alice[i] == "a":
    while alice[i] == "a":
    	alice.pop(i)
    
  elif alice[i] == "b":
    alice.pop(i)
    if bob[i] == "b":
      while bob[i] == "b":
      	bob.pop(i)
    elif bob[i] == "a":
      while bob[i] == "a":
        alice.pop(i)
    elif bob[i] == "c":
       while bob[i] == "c":
        charlie.pop(i)
      
  elif alice[i] == "c":
    alice.pop(i)
    if charlie[i] == "c":
      while charlie[i] == "c":
        charlie.pop(i)
    elif charlie[i] == "b":
      while charlie[i] == "b":
        bob.pop(i)
    elif charlie[i] == "a":
      while charlie[i] == "a":
        alice.pop(i)

for i in range(len(alice)):
	if len(alice) == 0 and alice[ 

### FIXED CODE ###

a = list(input())
b = list(input())
c = list(input())

win = False # if win == True, someone will win
run = a

while win != True:
  if run[0] == "a":
    run.pop(0)
    run = a # reset run
    if len(a) == 0:
      print("A")
      win = True
  elif run[0] == "b":
    run.pop(0)
    run = b
    if len(b) == 0:
      print("B")
      win = True
  else:
    run.pop(0)
    run = c
    if len(c) == 0:
      print("C")
      win = True
def LCS():
  x = raw_input()
  y = raw_input()
  X = len(x)
  Y = len(y)
  
  for i in range(X):
    c[i][0] = 0
  for j in range(Y):
    c[0][j] = 0

  for i in range(X):
    for j in range(Y):
      if X[i] == Y[i]: 
        c[i][j] = c[i - 1][j - 1] + 1

      elif:
        max(c[i - 1][j], c[i][j - 1])
        

  print c[X][Y]

q = input()

for i in range(q):
  LCS

  
    

### FIXED CODE ###

def LCS():
    X = raw_input()
    Y = raw_input()
 
    a, b = len(X), len(Y)
    c1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = X[i]
        c2 = c1+[]
        for j in range(b):
            if e1 == Y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
 
n = input()
for i in range(n):
    print LCS()
K = int(input())
a = [0]
out = '-1'
for n in range(1, K):
  a.append((a[n-1] + 7 * (10 ** (n-1)))%K)
for i in range(1, K):
  if a[i] == 0:
    out = i
  	break
print(out)

### FIXED CODE ###

K = int(input())
ans = '-1'
mod = 7%K
path = [mod]
for i in range(1,K+1):
  if mod == 0:
    ans = i
    break
  mod = (mod*10 + 7)%K
  path.append(mod)
  if mod == path[0]:
    ans = '-1'
    break
print(ans)
from collections import defaultdict
N, P = map(int,input().split())
S = input()

if P==5:
    ans = 0
    for i,m in enumerate(S):
        if m == '5' or m == '0':
            ans += i+1
elif P==2:
    ans = 0
    for i,m in enumerate(S):
        if int(m) % 2 ==0:
            ans += i+1
else:
    #primdic = defaultdict(int)
    primdic = [0]*N
    for i in range(N):
        # i~右端までの数字のmodP
        primdic[int(S[i:])%P] += 1
    primdic[0] += 1
    ans = 0
    #for value in primdic.values():
    #    ans += value*(value-1)//2
    for value in primdic:
        ans += value*(value-1)//2
print(ans)

### FIXED CODE ###

from collections import defaultdict
N, P = map(int,input().split())
S = input()

if P==5:
    ans = 0
    for i,m in enumerate(S):
        if m == '5' or m == '0':
            ans += i+1
elif P==2:
    ans = 0
    for i,m in enumerate(S):
        if int(m) % 2 ==0:
            ans += i+1
else:
    S = S[::-1]
    primdic = defaultdict(int)
    before = 0
    for i in range(0,N):
        now = (int(S[i])*pow(10,i,P)+before)%P
        primdic[now] += 1
        before = now
    # 文字なしの時はあまり0なので
    primdic[0] += 1
    ans = 0
    for value in primdic.values():
        ans += value*(value-1)//2
print(ans)
import numpy as np
h,w=map(int,input().split())
INF=10**10
a=[[INF for i in range(w)] for j in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]=="#":
            a[i][j]=0
for i in range(h):
    for j in range(w):
        k=a[i][j]+1

        if i!=h-1:
            if k<a[i+1][j]:
                a[i+1][j]=k

        if j!=w-1:
            if k<a[i][j+1]:
                a[i][j+1]=k

for i_ in range(h):
    for j_ in range(w):
        i=h-1-i_
        j=w-1-j_
        k=a[i][j]+1
        if i!=0:
            if k<a[i-1][j]:
                a[i-1][j]=k

        if j!=0:        
            if k<a[i][j-1]:
                a[i][j-1]=k


arr=np.array(a)
ans=arr.max()
print(ans)

### FIXED CODE ###

h,w=map(int,input().split())
INF=10**10
a=[[INF for i in range(w)] for j in range(h)]
ans=0
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]=="#":
            a[i][j]=0
            
for i in range(h):
    for j in range(w):
        k=a[i][j]+1

        if i!=h-1:
            if k<a[i+1][j]:
                a[i+1][j]=k
        if j!=w-1:
            if k<a[i][j+1]:
                a[i][j+1]=k

for i in range(h):
    for j in range(w):
        k=a[-1-i][-1-j]+1
        if i!=h-1:
            if k<a[-i-2][-j-1]:
                a[-i-2][-j-1]=k

        if j!=w-1:        
            if k<a[-i-1][-j-2]:
                a[-i-1][-j-2]=k

for i in range(h):
    ans=max(ans,max(a[i]))
print(ans)
#!/usr/bin/env python3
import sys
import itertools

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return set(i for i in range(n + 1) if is_prime[i])

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

def solve(A: int, B: int):
    G = gcd(A,B)
    P = primes(G)

    n = 1
    for p in P:
        if A % p == 0 and B % p == 0:
            n += 1

    print(n)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(n+1):
        if is_prime[i]:
            yield i

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

def cf(x1,x2):
    for i in range(1,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            yield i

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

def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a


def solve(A: int, B: int):
    AP = prime_factorize(A)
    BP = prime_factorize(B)
    print(len(AP & BP) + 1)

    return



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()
n = input()
s = raw_input().strip()
r = 0
for i in xrange(n):
  if s[i] == 'R': r += 1
  else: b += 1

if r > b: print "Yes"
else: print "No"

### FIXED CODE ###

n = input()
s = raw_input().strip()
r = b = 0
for i in xrange(n):
  if s[i] == 'R': r += 1
  else: b += 1
     
if r > b: print "Yes"
else: print "No"
n=int(input())
d=list(map(int,input().split()))
m=int(n/2)
d=sorted(d)
print(d[m+1]-d[m])


### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
m=int(n/2)
d=sorted(d)
print(d[m]-d[m-1])
s = input()
t = input()
print(t+s)

### FIXED CODE ###

s,t = input().split()
print(t+s)
n,k = map(int,input().split())
mod = 10**9 + 7

b = k
r = n - k

from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

a = cmb(n,k)

for i in range(b):
    ans = cmb(r+1,i+1) * cmb(b-1,i)
    print(ans%mod)

### FIXED CODE ###

n,k = map(int,input().split())
mod = 10**9 + 7

b = k
r = n - k

from operator import mul
from functools import reduce
def cmb(n,r):
    if n<r:
        return 0
    else:
        r = min(n-r,r)
        if r == 0: return 1
        over = reduce(mul, range(n, n - r, -1))
        under = reduce(mul, range(1,r + 1))
        return over // under

# a = cmb(n,k)
# print(a)

for i in range(b):
    ans = cmb(r+1,i+1) * cmb(b-1,i)
    print(ans%mod)
a,b=map(int,input().split())
print(max(a+b,a-b,a＊b))

### FIXED CODE ###

a,b=map(int,input().split())
print(max(a+b,a-b,a*b))
# -*- coding: utf-8 -*-
# 桁数の入力
a = input()
# スペース区切りの整数の入力
b = input().split()
b = list(map(int, b))
print(max(a) - min(a))

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 桁数の入力
a = input()
# スペース区切りの整数の入力
b = input().split()
b = list(map(int, b))
print(max(b) - min(b))
N=int(input())
L=list(map(int,input().split()))
count=0
a!=b, b!=c, c!=a
for a in range(N):
    for b in range(N):
        for c in range(N):
            if L[a]>(L[b]+L[c]),L[b]>(L[a]+L[c]),L[c]>(L[b]+L[a]):
                count=count+1
            else:
                continue
print(count)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
count=0
for a in range(N):
    for b in range(N):
        for c in range(N):
            if L[a]<(L[b]+L[c]) and L[b]<(L[a]+L[c]) and L[c]<(L[b]+L[a]) and L[a]!=L[b] and L[a]!=L[c] and L[c]!=L[b] and a<b<c:
                count=count+1
            else:
                continue
print(count)
n,m=map(int,input().split())
a=[input() for i in range(n)]
b=[input() for i in range(m)]
ans="No"
for i in range(n-m+1):
  for j in range(n-m+1):
    if [line[j:j+m] for line in a[i:i+m]]==B:
      ans="Yes"
      break
  if ans=="Yes":
    break
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
a=[input() for i in range(n)]
b=[input() for i in range(m)]
ans="No"
for i in range(n-m+1):
  for j in range(n-m+1):
    if [line[j:j+m] for line in a[i:i+m]]==b:
      ans="Yes"
      break
  if ans=="Yes":
    break
print(ans)
N=int(input())
a=str(N)
for i in range(1,4):
  if a[i]=7:
    print("Yes")
    break
print("No")
   

### FIXED CODE ###

N=int(input())
a=str(N)
if '7' in a:
  print("Yes")
else:
  print("No")
N,K = map(int,input().split())
H = list(map(int,input().split()))
inf = 10**9+7
dp = [inf] * (N+10)
dp[0] = 0
import numpy as np

for i,h in enumerate(H):
    for j in range(1,K+1):
        if i+j < N:
            dp[i+j] = min(dp[i+j],dp[i] + np.abs(h-H[i+j]))

print(dp[N-1])

### FIXED CODE ###

#import sys 
#input = sys.stdin.readline

N,K = map(int,input().split())
h = list(map(int,input().split()))

dp = [0] * 100010

dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2,min(K,N)):
    Minimum = dp[i-1]+abs(h[i]-h[i-1])
    for j in range(2,i+1):
        Minimum = min(dp[i-j]+abs(h[i]-h[i-j]),Minimum)
    dp[i] = Minimum
if N > K:
    if K == 1:
        for i in range(K,N):
            Minimum = dp[i-1]+abs(h[i]-h[i-1])
            dp[i] = Minimum
        
    else:
        for i in range(K,N):
            Minimum = dp[i-1]+abs(h[i]-h[i-1])
            for (j,k) in zip(dp[i-K:i-1],h[i-K:i-1]):
                Minimum = min(j+abs(h[i]-k),Minimum)
            dp[i] = Minimum
        
print(dp[N-1])
def main():
  A,B = map(int,input.split())
  
  B*=100
  
  print((A*B)//100)
  return

main()

### FIXED CODE ###

A,B = input().split()
A = int(A)
B = round(float(B)*100)

res = (A*B)//100
print(res)
P = []
S = []
for i in range(2):
    pp, ss  = map(int, input().split())
    P.append(pp)
    S.append(ss)

A = P[0]
V = S[0]
B = P[1]
W = S[1]
T = int(input())

print(A)
print(V)
print(B)
print(W)
print(T)

def run():
	if A < B:
		c = (B + V*T) - (A + W*T)
		if c <= 0 :
			return 'YES'
		else :
			return 'NO'
	elif A > B:
		c = (A - W*T) - (B - V*T)
		if c <= 0 :
			return 'YES'
		else :
			return 'NO'
	else :
		return 'YES'
print(run())

### FIXED CODE ###

a = input()
nickname = a[0:3]
print(nickname)
n, k = map(int, input().split())
s = input()

s = '1' + s + '1'

cnt_1 = []
cnt_0 = []
stack_1 = 0
stack_0 = 0
for i in s:
    if i == '1':
        if stack_0 > 0:
            cnt_0.append(stack_0)
            stack_0 = 0
        stack_1 += 1
    else:
        if stack_1 > 0:
            cnt_1.append(stack_1)
            stack_1 = 0
        stack_0 += 1
if stack_1 > 0:
    cnt_1.append(stack_1)
cnt_1[0] -= 1
cnt_1[-1] -= 1
if len(cnt_1) == 0 or len(cnt_0) == 0:
    print(n)
    exit()
cum_1 = []
cum_0 = []
for i in range(len(cnt_1)-k):
    cum_1.append(sum(cnt_1[i:i+k+1]))
for i in range(len(cnt_0)-k+1):
    cum_0.append(sum(cnt_0[i:i+k]))

res = []
for v, w in zip(cum_1, cum_0):
    res.append(v+w)
print(max(res))

### FIXED CODE ###

n, k = map(int, input().split())
s = input()

s = '1' + s + '1'

cnt_1 = []
cnt_0 = []
stack_1 = 0
stack_0 = 0
for i in s:
    if i == '1':
        if stack_0 > 0:
            cnt_0.append(stack_0)
            stack_0 = 0
        stack_1 += 1
    else:
        if stack_1 > 0:
            cnt_1.append(stack_1)
            stack_1 = 0
        stack_0 += 1
if stack_1 > 0:
    cnt_1.append(stack_1)

if len(cnt_1) == 0 or len(cnt_0) == 0:
    print(n)
    exit()
cnt_1[0] -= 1
cnt_1[-1] -= 1

if k > len(cnt_0):
    k = len(cnt_0)
cum_1 = [sum(cnt_1[:k+1])]
cum_0 = [sum(cnt_0[:k])]
for i in range(1, len(cnt_1)-k):
    cum = cum_1[i-1] + cnt_1[i+k] - cnt_1[i-1]
    cum_1.append(cum)
for i in range(1, len(cnt_0)-k+1):
    cum = cum_0[i-1] + cnt_0[i+k-1] - cnt_0[i-1]
    cum_0.append(cum)
res = []

for v, w in zip(cum_1, cum_0):
    res.append(v+w)
print(max(res))
def main():
    N, M = map(int, input().split())
    A = [input() for _ in range(N)]
    B = [input() for _ in range(M)]
    for i in range(N):
        for j in range(N):
            f = True
            for k in range(M):
                for l in range(M):
                    if A[i + k][j + l] != B[k][l]:
                        f = False
                        break
                if f is False:
                    break
            if f is True:
                print('Yes')
                exit()
    print('No')


main()


### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    A = [input() for _ in range(N)]
    B = [input() for _ in range(M)]
    for i in range(N):
        for j in range(N):
            f = True
            for k in range(M):
                for l in range(M):
                    if i + k >= N or j + l >= N:
                        f = False
                        break
                    if A[i + k][j + l] != B[k][l]:
                        f = False
                        break
                if f is False:
                    break
            if f is True:
                print('Yes')
                exit()
    print('No')


main()
import math
n = int(input())
ary = [int(input()) for _ in range(n)]
ans = 1
for i in ary:
    ans = (ans*i)//math.gcd(ans,i)
print(ans)

### FIXED CODE ###

import fractions
n = int(input())
ans = 1
for i in range(n):
    a = int(input())
    ans = ans // fractions.gcd(ans,a) * a
print(ans)
N=int(input())
A=map(int,input().split())
ans=A[0]
for i in range(1,N):
  s=ans
  t=A[i]
  if t%ans!=0:
    s=t%ans
  t=A[i]
  if ans%t!=0:
    t=t%ans
  ans=min(s,t)
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
a=min(A)
S={n%a for n in A if n%a!=0}

while len(S)>0:
    tmp=a
    a=min(S)
    S={n%a for n in S if n%a!=0}
    if tmp%a!=0:
        S.add(tmp%a)
print(a)
import sys
input = sys.stdin.readline

s = list(input().strip())
q=int(input())
for i in range(q):
    L = list(input().rstrip().split())    
    if L[0]=='1':
        s.reverse
    else:
        a,b,c = L
        if int(b)==2:
            s.append(c)
        else:
            s.insert(0,c)
            s = "".join(s)
print(s)
            
            


### FIXED CODE ###

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

s = deque(input().strip())
q=int(input())
count = 0
for i in range(q):
    L = list(input().rstrip().split())    
    if L[0]=='1':
        count += 1
    else:
        a,b,c = L
        b = int(b)
        if count&1==1:
            b=3-b
        if b==2:
            s.append(c)
        else:
            s.appendleft(c)
if count&1==1:
    print("".join(list(s)[::-1])) 
else:
    print("".join(s))
from collections import deque

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

Q = deque(range(N))

days = [0]*N  # 各選手の現在の日付
pairs = [0]*N  # 次の対戦相手を管理(wait的な)

while Q:
    x = Q.popleft()  # 試合する人
    if len(matches(x)) == 0:  # 試合が全て終わってる?
        continue
    y = matches[x].pop(0)  # xの次の対戦相手
    if pairs[y] == x:
        day = max(days[x], days[y])+1
        days[x] = day
        days[y] = day
        Q.append(x)
        Q.append(y)
    else:
        pairs[x] = y

if not any(matches):  # 全ての試合をしょうか
    print(max(days))
else:
    print(-1)


### FIXED CODE ###

from collections import deque

n = int(input())
matches = []
for _ in range(n):
    matches.append(list(map(lambda x: int(x)-1, input().split())))

q = deque(range(n))

days = [0]*n  # 各選手の現在の日付
pairs = [-1]*n  # 次の対戦相手を管理(wait的な)

while q:
    x = q.popleft()  # 試合する人
    if len(matches[x]) == 0:  # 試合が全て終わってる?
        continue
    y = matches[x].pop(0)  # xの次の対戦相手
    if pairs[y] == x:
        day = max(days[x], days[y])+1
        days[x] = day
        days[y] = day
        q.append(x)
        q.append(y)
    else:
        pairs[x] = y

if not any(matches):  # 全ての試合をしょうか
    print(max(days))
else:
    print(-1)