Problem:


Score : 500 points

Problem Statement

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 1

3
2 3
1 3
1 2

Sample Output 1

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.

Sample Input 2

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

Sample Output 2

4

All the conditions can be satisfied if the matches are scheduled for four days as follows:

Day 1: Player 1 vs Player 2, Player 3 vs Player 4

Day 2: Player 1 vs Player 3

Day 3: Player 1 vs Player 4, Player 2 vs Player 3

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

#define cc(x) cout << (x) << endl
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define repi(i,a,b) for(int i = int(a); i < int(b); ++i)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef vector<long long> vll;

template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

const ll inf = 1LL<<58;
const int iinf = 1<<30;

int main(){
    ll n;
    cin >> n;
    ll now[n][2];
    ll a[n][n-1];
    rep(i,n){
        rep(j,n-1){
            cin >> a[i][j];
        }
    }
    ll end=n*(n-1)/2;
    ll nex=0;
    ll day=0;
    ll sumsiai=0;
    ll siaisuu=0;
    ll minusnex=0;
    while(1){
        day++;
        siaisuu=sumsiai;
        rep(i,n){
            if(now[i][0]==n-1 || now[i][1]== day){
                continue;
            }
            nex=a[i][now[i][0]];
            minusnex=nex-1;
            if(i+1==a[nex-1][now[minusnex][0]] && now[minusnex][1] != day){
                siaisuu+=1;
                now[i][0]+=1;
                now[i][1]=day;
                now[minusnex][1]=day;
                now[minusnex][0]+=1;
            }
        }
        if(siaisuu-sumsiai==0){
            cout << -1;
            break;
        }

    if(siaisuu==end){
        cout << day;
        break;
    }
    sumsiai=siaisuu;
    }
}

Submission status: Runtime Error

Solution code:
from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline

def main():
    n=int(input())
    d=[deque(map(int,input().split()))for i in range(n)]

    c=0
    immortalskip=set()
    while any(d):
        c+=1
        f=0
        skip=set()
        for i in range(n):
            if i not in skip.copy() and i not in immortalskip:
                if d[i]:
                    if d[i][0] in skip:
                        continue
                    elif i==d[d[i][0]-1][0]:
                        oppo=d[i].popleft()
                        d[oppo].popleft()
                        skip.add(oppo)
                        skip.add(i)
                        f=1
                else:
                    immortalskip.add(i)
#            print(c,i,d,skip,f)
        if not f:
            print(-1)
            exit()

    print(c)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
ans = 0
tmp = 0
total = (N * (N - 1)) // 2

for i in range(N):
    sLst = [0] * N
    for j in range(N):
        if len(a[j]) != 0 and len(a[a[j][0] - 1]) != 0:
            if sLst[j] == 0 or sLst[a[a[j][0] - 1][0]] == 0:
                if a[a[j][0] - 1][0] == j + 1:
                    sLst[j] = a[j].pop(0)
                    sLst[a[a[j][0] - 1][0]] = a[a[j][0] - 1].pop(0)
                    tmp += 1
                    total -= 1
    if total == 0:
        break

    if tmp == 0:
        print(-1)
        exit()
    ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys

N = int(input())
A = []
for i in range(N):
    Ai = [int(v) - 1 for v in input().split()]
    A.append(Ai)

deps = {}
for i in range(N):
    prevmatch = (i, i)
    for j in range(len(A[i]) - 1, -1, -1):
        if A[i][j] > i:
            match = (i, A[i][j])
        else:
            match = (A[i][j], i)
        deps.setdefault(prevmatch, []).append(match)
        prevmatch = match


def fn(match, day, hist):
    if match in hist:
        print('-1')
        sys.exit()
    hist.add(match)

    if match in days and days[match] >= day:
        return
    days[match] = day

    global maxday
    if maxday < day:
        maxday = day

    for depmatch in deps.get(match, []):
        fn(depmatch, day + 1, hist.copy())


days = {}
maxday = 0
for i in range(N):
    fn((i, i), 0, set())
print(maxday)

Submission status: Runtime Error

Solution code:
a = int(input())
b = [[int(i) for i in input().split()] for _ in range(a)]
print(b)
counter = 0
while len(b) != 0:
    found = False
    done = [False] * len(b)
    for i in range(len(b)):
        if len(b[i]) >= 1 and not done[i]:
            target = b[i][0]-1
            if not done[target]:
                b[i].pop(0)
                b[target].pop(0)
                done[i] = True
                done[target] = True
                found = True
    if not found:
        break
    counter += 1
if not found:
    print(-1)
else:
    print(counter)

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
alist = []
for i in range(n):
    alist.append(list(map(int, input().split())))

point = 0
kazu = 0
while True:
    y = []
    for i in range(n):
        if i not in y and len(alist[i]) > 0:
            for j in range(i, n):
                if j not in y and len(alist[j]) > 0:
                    if alist[i][0] - 1 == j and alist[j][0] - 1 == i:
                        alist[i].pop(0)
                        alist[j].pop(0)
                        y.append(i)
                        y.append(j)
                        point += 1
    if len(y) == 0:
        print(-1)
        sys.exit()
    kazu += 1
    if n*(n-1)/2 == point:
        print(kazu)
        sys.exit()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()
	A = []
	for i in range(N):
		tmp = inputList()
		A.append(tmp)

	ind = [0] * N
	ans = 0

	for i in enumerate(10000):
		flg = False
		doList = []

		for i, val in enumerate(ind):
			if val == -1:
				continue

			min = A[i]
			target = min[val]

			if (A[target-1][ind[target-1]] - 1) == i:
				if (i not in doList) and (target-1 not in doList):
					if ind[i]+1 > N-2:
						ind[i] = -1
					else:
						ind[i] += 1

					if ind[target-1]+1 > N-2:
						ind[target-1] = -1
					else:
						ind[target-1] += 1

					doList.append(i)
					doList.append(target-1)
					flg = True

		if flg == True:
			ans += 1
		else:
			break

	for i in ind:
		if i != -1:
			print(-1)
			sys.exit()

	print(ans)



if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input = lambda: sys.stdin.readline()[:-1]
n=int(input())
data=[deque(map(int,input().split())) for i in range(n)]
last=n*(n-1)
count=0
while last:
	flag=1
	count+=1
	taisenzumi=[0]*n
	for i in range(n):
		if data[i]:
			if data[aite-1][0]==i+1:
				if taisenzumi[i]:continue
				if taisenzumi[aite-1]:continue				
				aite=data[i][0]
				data[i].popleft()
				data[aite-1].popleft()
				taisenzumi[aite-1]=1
				taisenzumi[i]=1
				last-=2
				flag=0
			else:continue
	if flag:
		break
else:
	print(count)
	exit()
print(-1)

Submission status: Runtime Error

Solution code:
def solve(A, N, day=0):
    # check if end
    if all([len(a) == 0 for a in A]):
        return day
    # get available games
    available_games = set()
    for player in range(N):

        if len(A[player]) == 0:
            continue

        opponent = A[player][0]

        if opponent == player or len(A[opponent]) == 0:
            continue

        if A[opponent][0] == player:
            if player > opponent:
                player, opponent = opponent, player
            available_games.add((player, opponent))
    if len(available_games) == 0:
        return -1

    for game in available_games:
        player, opponent = game
        A[player].pop(0)
        A[opponent].pop(0)
    return solve(A, N, day + 1)


if __name__ == '__main__':
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    for i in range(N):
        for j in range(N - 1):
            A[i][j] -= 1

    answer = solve(A, N)
    print(answer)

Submission status: Runtime Error

Solution code:
import sys

N = int(input())
A = []
for i in range(N):
    Ai = [int(v) - 1 for v in input().split()]
    A.append(Ai)

deps = {}
for i in range(N):
    prevmatch = (i, i)
    for j in range(len(A[i]) - 1, -1, -1):
        if A[i][j] > i:
            match = (i, A[i][j])
        else:
            match = (A[i][j], i)
        deps.setdefault(prevmatch, []).append(match)
        prevmatch = match


def fn(match, day, hist):
    if match in hist:
        print('-1')
        sys.exit()
    hist.add(match)

    if match in days and days[match] >= day:
        return
    days[match] = day

    for depmatch in deps.get(match, []):
        fn(depmatch, day + 1, hist.copy())


days = {}
for i in range(N):
    fn((i, i), 0, set())
print(max(days.values()))

Submission status: Runtime Error

Solution code:
import math
N = int(input())
D = [list(map(int,input().split())) for i in range(N)]
ans = 0
x,y = 0,0
for d in D:
    if d[0]>=0 and d[1]>=0:
        x+=d[0]
        y+=d[1]
ans = max(ans,x*x+y*y)
x,y = 0,0
for d in D:
    if d[0]>=0 and d[1]<=0:
        x+=d[0]
        y+=d[1]
ans = max(ans,x*x+y*y)
x,y = 0,0
for d in D:
    if d[0]<=0 and d[1]>=0:
        x+=d[0]
        y+=d[1]
ans = max(ans,x*x+y*y)
x,y = 0,0
for d in D:
    if d[0]<=0 and d[1]<=0:
        x+=d[0]
        y+=d[1]
ans = max(ans,x*x+y*y)
import math
N = int(input())
D = [list(map(int,input().split())) for i in range(N)]
ans = 0
x,y = 0,0
for d in D:
    if d[0]>=0 and d[1]>=0:
        x+=d[0]
        y+=d[1]
ans = max(ans,x*x+y*y)
x,y = 0,0
for d in D:
    if d[0]>=0 and d[1]<=0:
        x+=d[0]
        y+=d[1]
ans = max(ans,x*x+y*y)
x,y = 0,0
for d in D:
    if d[0]<=0 and d[1]>=0:
        x+=d[0]
        y+=d[1]
ans = max(ans,x*x+y*y)
D.sort(key=lambda x:abs(x[0])+abs(x[1]))
x,y,k = 0,0,0
for d in D:
    if k<(x+d[0])**2+(y+d[1])**2:
        x+=d[0]
        y+=d[1]
        k = x*x+y*y
ans = max(ans,k)
x,y,k = 0,0,0
for d in D:
    if k<=(x+d[0])**2+(y+d[1])**2:
        x+=d[0]
        y+=d[1]
        k = x*x+y*y
ans = max(ans,k)
print(math.sqrt(ans))

Submission status: Runtime Error

Solution code:
for i in range(N):
    a_list.append(list(map(int, input().split())))

c = 0
z_list = []
while(1):
    c += 1
    alr_list = []
    for i in range(N):
        if i in z_list:
            continue
        if i in alr_list:
            continue
        i_a = a_list[i][0] - 1
        if i_a in z_list:
            continue
        if i_a in alr_list:
            continue
        if i+1 == a_list[i_a][0]:
            a_list[i].pop(0)
            a_list[i_a].pop(0)
            if len(a_list[i]) == 0:
                z_list.append(i)
            if len(a_list[i_a]) == 0:
                z_list.append(i_a)
            alr_list.append(i)
            alr_list.append(i_a)
    if len(z_list) == N:
        break
    if len(alr_list) == 0:
        c = -1
        break
print(c)

Submission status: Runtime Error

Solution code:
N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		edge[match_dict[(x,y)]].append(match_dict[(z,w)])
		parent[match_dict[(z,w)]].append(match_dict[(x,y)])
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
day = 0
while len(candidate) > 0:
	new_candidate = []
	for c in candidate:
		if finish[c]:
			continue
		finish[c] = True
		for e in edge[c]:
			if finish[e]:
				continue
			if all([finish[p] for p in parent[e]])
				new_candidate.append(e)
	day += 1
	candidate = new_candidate

all_finished = sum([1 if f else 0 for f in finish]) == M
if all_finished:
	print(day)
else:
	print(-1)

Submission status: Runtime Error

Solution code:
import sys

N = int(input())
A = []
for i in range(N):
    Ai = [int(v) - 1 for v in input().split()]
    A.append(Ai)

deps = {}
for i in range(N):
    prevmatch = (i, i)
    for j in range(len(A[i]) - 1, -1, -1):
        if A[i][j] > i:
            match = (i, A[i][j])
        else:
            match = (A[i][j], i)
        deps.setdefault(prevmatch, []).append(match)
        prevmatch = match


def fn(match, day, hist):
    if match in hist:
        print('-1')
        sys.exit()
    hist.add(match)

    if match not in days or days[match] < day:
        days[match] = day
    else:
        day = days[match]

    for depmatch in deps.get(match, []):
        fn(depmatch, day + 1, hist.copy())


days = {}
for i in range(N):
    fn((i, i), 0, set())
print(max(days.values()))

Submission status: Runtime Error

Solution code:
N = int(input())

a_list = []
for i in range(N):
    a_list.append(list(map(int, input().split())))

c = 0
z_list = []
while(1):
    c += 1
    alr_list = []
    for i in range(N):
        if i in z_list:
            continue
        if i in alr_list:
            continue
	i_a = a_list[i][0] - 1
        if i_a in z_list:
            continue
        if i_a in alr_list:
            continue
        if i+1 == a_list[i_a][0]:
            a_list[i].pop(0)
            a_list[i_a].pop(0)
            if len(a_list[i]) == 0:
                z_list.append(i)
            if len(a_list[i_a]) == 0:
                z_list.append(i_a)
            alr_list.append(i)
            alr_list.append(i_a)
    if len(z_list) == N:
        break
    if len(alr_list) == 0:
        c = -1
        break
print(c)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[]
hd=[0]*n
for i in range(n):
    a.append(tuple(map(int,input().split())))
loop=0
flag=0
while(flag<n):
    stk=[]
    for i in range(n):
        idx=a[i][hd[i]]-1
        if a[idx][hd[idx]]==i+1:
            stk.append(i)
    if not stk:
        loop=-2
        break
    for j in stk:
        hd[j]+=1
        if hd[j]==n-2:
            flag+=1
    loop+=1
print(loop+1)

Submission status: Runtime Error

Solution code:
def solve(A, N, day=0):
    # check if end
    if all([len(a) == 0 for a in A]):
        return day
    # get available games
    available_games = set()
    for i in range(N):

        if len(A[i]) == 0:
            continue

        j = A[i][0]

        if len(A[j]) == 0:
            continue

        if A[j][0] == i:
            if i > j:
                i, j = j, i
            available_games.add((i, j))
    if len(available_games) == 0:
        return -1

    for game in available_games:
        i, j = game
        A[i].pop(0)
        A[j].pop(0)
    return solve(A, N, day + 1)


if __name__ == '__main__':
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    for i in range(N):
        for j in range(N - 1):
            A[i][j] -= 1

    answer = solve(A, N)
    print(answer)

Submission status: Runtime Error

Solution code:

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

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

    # check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
    check = [0] * N #i番目の次の相手のindex

    ans = 0
    i = 0
    tmp = 0
    count = 0
    while tmp < 2 * N + 2:
        if tmp > N + 500:
            i += 290
        if i % N == 0:
            ans += 1
            flag  = [True] * N #試合をしたかどうかチェック
            i = 0
            
        if check[i] >= N - 1 or flag[i] == False:
            i += 1
            tmp += 1
            continue
        b = A[i][check[i]]
        # print (b)
        if A[b - 1][check[b - 1]] - 1 == i and flag[b - 1]: #試合できる時
            check[i] += 1
            check[b - 1] += 1
            flag[i] = False
            flag[b - 1] = False
            tmp = 0
            count += 1
            if count == (N * (N - 1))//2:
                print (ans)
                exit()
        i += 1
        tmp += 1
    
    print (-1)
    return 
            
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from queue import deque
import numpy as np
N = int(input())
A = {}
for i in range(1,N+1):
    A[i] = deque(map(int,input().split()))
# print(A)

GAME = N*(N-1)//2
cnt = 0
ans = 0
cnt2 = 0
while cnt < GAME:
    ok = np.array([True]*N,dtype='?')
    for i in range(1,N+1):
        if A[i] and ok[i-1]:
            t = A[i][0]
            if ok[t-1] and A[t] and i == A[t][0]:
                A[i].popleft()
                A[t].popleft()
                cnt += 1
                ok[i-1] = False
                ok[t-1] = False
    ans += 1
    cnt2 += 1
    if cnt2 > GAME:
        ans = -1
        break
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())

game = [0]

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

count = 0
final = n*(n-1)//2
for day in range(1, 1000000):
    finish = set()
    possible = False
    for me in range(1, n+1):
        if me in finish or game[me] == []:
            continue

        you = game[me][-1]
        if you in finish:
            continue
        else:
            if game[you][-1] == me:
                finish.add(game[you].pop())
                finish.add(game[me].pop())
                possible = True
                count += 1
            else:
                contin
    if not possible:
        print(-1)
        exit()

    if count == final:
        print(day)
        exit()

Submission status: Runtime Error

Solution code:
import sys,copy
input = sys.stdin.readline
#-------------------------------------

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

day = 0
done = 0
b = a

while(True):
    a = b
    b = copy.deepcopy(a)
    progress = 0
    day += 1
    # print("day",day)
    for i,v in enumerate(a):
        # print(i)
        if i == 0 : continue
        target = v[ n-1 - v[n-1] ]
        target2 = a[target][n-1 - a[target][n-1]]
        if target2 == i:
            # print(i)
            progress = 1
            # b[i][n-1 - v[n-1]] = 0
            b[i][n-1] -= 1
            if b[i][n-1] == 0:
                done += 1
    # print(b)
    if progress == 0:
        day = -1
        break
    if done == n:
        break

print(day)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import copy
# Your code here!
n=int(input().rstrip())
a=[]


for i in range(n):
    
    a.append(input().rstrip().split(" "))
    for j in range(n-1):
        a[i][j]=int(a[i][j])
ans=0
day=0
last=int(n*(n-1)/2)
cnt=[[0 for i in range(n)]for j in range (last)]

while(not last==0):
    olast=last
    day=day+1
    #for i in range(n):
    #    cnt[i]=0
    for i in range(n):
        if(cnt[i][day]==1 or len(a[i])==0):
            continue
        else:
            s=a[i][0]
            if(len(a[s-1])==0 or cnt[s-1][day]==1):
                continue
            if( i+1==a[s-1][0] and s==a[i][0]  ):
                cnt[i][day]=1
                cnt[s-1][day]=1
                last=last-1
                del a[i][0]
                del a[s-1][0]
    #print(a)
    #print(last)
    if(last==olast):
        day=-1
        break
    
    
print(day)

Submission status: Runtime Error

Solution code:
n=int(input())
r=[]
a=[]
b=[]
for i in range(n*3):
  r.append([int(i) for i in input().split()])
for i in range(n):
  k=[]
  f=[]
  for j in range(n):
    if len(r[j])!=0:
      p=r[j][0]-1
      if r[p][0]==j+1:
        if j+1 not in f:
          if p+1 not in f:
            k.append([r[j].pop(0),r[p].pop(0)])
            f.append(j+1)
            f.append(p+1)
  if len(k)==0:
    break
  else:
    for o in k:
      a.append(o)
    b.append(k)
if len(a)==(n*(n-1)//2):
  print(len(b))
else:
  print('-1')

Submission status: Runtime Error

Solution code:
N = int(input())
As = [[]]
for i in range(N):
    As.append(list(map(int, input().split())))

Cs = [0] * (N + 1)
d = 1
ms = 0
msMax = N * (N - 1) // 2
sw = True
while sw:
    tab = set()
    c = 0
    for i in range(1, N + 1):
        if Cs[i] == N - 1:
            continue
        a = 0
        b = 0
        if i > As[i][Cs[i]]:
            a = As[i][Cs[i]]
            b = i
        else:
            a = i
            b = As[i][Cs[i]]
        if (a, b) in tab:
            ms = ms + 1
            c = c + 1
            if ms == msMax:
                sw = False
                break
            Cs[a] += 1
            Cs[b] += 1
        else:
            tab.add((a, b))
    if c == 0:
        d = 0
        break
    d += 1
print(d - 1)    N = int(input())
    As = [[]]
    for i in range(N):
        As.append(list(map(int, input().split())))

    Cs = [0] * (N + 1)
    Ks = [False] * (N + 1)
    d = 1
    ms = 0
    msMax = N * (N - 1) // 2
    sw = True
    tab = set()
    while sw:
        c = 0
        wa = []
        for i in range(1, N + 1):
            if Ks[i]:
                continue
            if Cs[i] == N - 1:
                continue
            a = 0
            b = 0
            if i > As[i][Cs[i]]:
                a = As[i][Cs[i]]
                b = i
            else:
                a = i
                b = As[i][Cs[i]]
            if (a, b) in tab:
                ms = ms + 1
                c = c + 1
                if ms == msMax:
                    sw = False
                    print(d)
                    break
                Cs[a] += 1
                Cs[b] += 1
                tab.remove((a, b))
                wa.append(a)
                wa.append(b)
            else:
                tab.add((a, b))
                Ks[i] = True
        for i in wa:
            Ks[i] = False
        d += 1
        if c == 0:
            print(-1)
            break

Submission status: Runtime Error

Solution code:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
from scipy.sparse import csr_matrix

dic = {}
for i in range(N):
    for j in range(i + 1, N):
        dic[(i, j)] = len(dic)


a = [[] for _ in range(N)]
for i, Ai in enumerate(A):
    for Aij in Ai:
        ind = dic[tuple(sorted([i, Aij - 1]))]
        a[i].append(ind)

data, row_ind, col_ind = [], [], []
for ai in a:
    for row, col in zip(ai, ai[1:]):
        data.append(-1)
        row_ind.append(row)
        col_ind.append(col)

g = csr_matrix((data, (row_ind, col_ind)), shape=(len(dic), len(dic)))

try:
    dist_matrix = bellman_ford(g)
    ans = -int(dist_matrix.min()) + 1
except NegativeCycleError:
    ans = -1

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
N=int(input())
M=(N*(N-1))//2
D=dict()
tmp=0
X=[(0,0) for i in range(M)]
G=[[] for i in range(M)]
for i in range(1,N+1):
    for j in range(1,N+1):
        if i<j:
            D[(i,j)]=tmp
            X[tmp]=(i,j)
            tmp+=1
A=[[int(j) for j in input().split()] for i in range(N)]
for i in range(N):
    for j in range(N-2):
        p1=D[(i+1,A[i][j])] if i+1<A[i][j] else D[(A[i][j],i+1)]
        p2=D[(i+1,A[i][j+1])] if i+1<A[i][j+1] else D[(A[i][j+1],i+1)]
        G[p1].append(p2)
K=[0 for i in range(M)]
for i in range(M):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(M) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)
#print(D)
#print(res)
if len(res)==0:
    print(-1)
    exit()
def isok(x,y):
    a,b=X[x]
    c,d=X[y]
    if len({a,b,c,d})<4:
        return False
    else:
        return True
invres=[0 for i in range(M)]
for i in range(M):
    invres[res[i]]=i
#print(invres)
Y=[0 for i in range(M)]
for i in res:
    for j in G[i]:
        Y[invres[j]]=max(Y[invres[j]],invres[i]+1)
#print(Y)
dp=[0 for i in range(M)]
dp[0]=M
ans=1
for i in range(1,M):
    flag=0
    for j in range(Y[i],i):
        if isok(res[i],res[j]):
            flag=1
            break
    if flag==0:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def main():
  input = sys.stdin.readline
  n = int(input())
  target_num = n*(n-1)//2

  all_set = set()
  a = [None] * n
  for i in range(n):
    a[i] = deque(map(int, input()))
  ans = 0

  while True:
    cur_set = set()
    flag = False
    for i in range(n):
      if len(a[i]):
        tup = tuple(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 not flag:
      print(-1)
      exit()

  print(ans)

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
n=int(input())
r=[]
a=[]
b=[]
for i in range(n):
  r.append([int(i) for i in input().split()])
for i in range(n):
  k=[]
  for j in range(n):
    p=r[j][0]
    if r[p][0]==j:
      k.append([r[j].pop(0),r[p].pop()])
  if len(k)==0:
    break
  else:
    a.append(o for o in k)
    b.append(k)
if len(a)==(n*(n+1)//2):
  print(len(b))
else:
  print(-1)

Submission status: Runtime Error

Solution code:
rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

from collections import deque
def solve(N, A):
    ans = 0
    todo = N * (N-1)
    to_inspect = range(N)
    while True:
        ans += 1
        found = False
        to_inspect2 = set()
        for i in to_inspect:
            row = A[i]
            if row:
                j = row[0]
                if (i not in to_inspect2 and j not in to_inspect2 and
                        A[j] and A[j][0] == i):
                    pairings[i] = j
                    pairings[j] = i
                    row.popleft()
                    A[j].popleft()
                    found = True
                    todo -= 2
                    to_inspect2.add(i)
                    to_inspect2.add(j)
        if not todo: return ans
        if not found: return -1
        to_inspect = to_inspect2


N = rri()
A = []
for _ in xrange(N):
    row = rrm()
    A.append(deque(x-1 for x in row))
print solve(N, A)