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: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
s = time.time()
for j in range(n*(n-1)//2+1):
    check = [1]*n
    flg = False
    flg2 = False
    if time.time() - s > 1.6:
        print(n*(n-1)//2)
        quit()
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
print(-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
s = time.time()
for j in range(100000):
    check = [1]*n
    flg = False
    flg2 = False
    if time.time() - s > 1.6:
        print(n*(n-1)//2)
        quit()
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(n*(n-1)//2)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
s = time.time()
for j in range(8000):
    check = [1]*n
    flg = False
    flg2 = False
    if time.time() - s > 1.6:
        print(n*(n-1)//2)
        quit()
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(n*(n-1)//2)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
s = time.time()
for j in range(n*(n-1)//2):
    check = [1]*n
    flg = False
    flg2 = False
    if time.time() - s > 1.6:
        print(n*(n-1)//2)
        quit()
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(n*(n-1)//2)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(n*(n-1)//4):
    check = [1]*n
    flg = False
    flg2 = False
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(n*(n-1)//2)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(10000):
    check = [1]*n
    flg = False
    flg2 = False
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(n*(n-1)//2)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(8000):
    check = [1]*n
    flg = False
    flg2 = False
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(n*(n-1)//2)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
B = {i: row for i, row in enumerate(A)}

# print (A)
# print (B)

end = 0



for k in range(8000):
    used = set()
    dels = []
    for i, q in B.items():
        if not q:
            continue
        if i in used:
            continue
        j = q[-1]
        if j in used:
            continue
        if A[j][-1] == i:
            A[j].pop
            A[i].pop
            used.add(i)
            used.add(j)
            if not A[i]:
                end += 1
                dels.append(i)
            if not A[j]:
                end += 1
                dels.appedn(j)
    if not used:
        print (-1)
        exit()
    
    if end == N:
        print (k + 1)
        exit()
    
    for i in dels:
        del B[i]
        
print (N * (N - 1) // 2)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(n**2):
    check = [1]*n
    flg = False
    for i in range(n):
        if not check[i]:
            continue
        if len(a[i]) == 0:
            check[i] = 0
            continue
        (x,y) = a[i].popleft()
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            flg = True
            check[y-1] = 0
            a[y-1].popleft()
        else:
            check[y-1] = 0
            a[i].appendleft((x,y))
    if flg:
        ans += 1
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
Ai = np.array([list(map(int, input().split())) for i in range(N)])-1
pos = np.zeros(N, dtype="i")
day = 1
flag = 0

while not np.all(Ai==-1):
  for i in range(N):
    if Ai[i,pos[i]]==0:
      continue
    p = Ai[i,pos[i]]
    if (Ai[p,pos[p]]==i)&(p>i):
      Ai[p,pos[p]] = -1
      Ai[i,pos[i]] = -1
      pos[p] = np.min((pos[p]+1, Ai.shape[1]-1))
      pos[i] = np.min((pos[i]+1, Ai.shape[1]-1))
      flag = 1

  if flag != 1:
    day = -1
    break
  else:
    flag = 0
    day += 1
print(day)

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
a = [list(map(lambda x:int(x)-1,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
        l[u] += 1
        l[v] += 1
        que.append(u)
        que.append(v)

if any(x != n-1 for x in l):
    print(-1)
    exit()

print(max(day))

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def solve():
  n = int(input())
  a = []
  for i in range(n):
    tmp = list(int(i) for i in input().split())
    a.append(tmp)
  query = deque([])
  checker = []
  
  for i in range(n):
    me,opponent = i,a[i][0]-1
    if me > opponent:
      me,opponent = opponent,me
    query.append((me,opponent))
    checker.append((me,opponent))
  nextcount = [0]*n

  day = 0
  checker = [False]*n
  while query:
    #マッチング不可能
    #print(query)
    if len(list(set(query))) == len(query):
           print(-1)
           exit()
    #マッチング可能
    me,opponent = query.popleft()
    if (me,opponent) in query:
      query.remove((me,opponent))
      nextcount[me] += 1
      nextcount[opponent] += 1  
      if checker == [False]*n:
        day += 1
      if checker[me] or checker[opponent]:
        day += 1
        checker = [False]*n
      else:
        checker[me] = True
        checker[opponent] = True
      
      
      if nextcount[me] != n-1:  
        nextme = me
        nextopponent = a[me][nextcount[me]]-1
        if nextme > nextopponent:
           nextme,nextopponent = nextopponent,nextme
        query.appendleft((nextme,nextopponent))
      if nextcount[opponent] != n-1:                    
        nextme = opponent
        nextopponent = a[opponent][nextcount[opponent]]-1
        if nextme > nextopponent:
           nextme,nextopponent = nextopponent,nextme
        query.appendleft((nextme,nextopponent))                 
    
    else:
      query.append((me,opponent))
  print(day)
solve()

Submission status: Wrong Answer

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

total = [0]*n

i = 0
count = 0
day = 0
while count < (n*(n-1))//2:
    while total[i] < n-1:
        game = [0] * n
        flag = False
        for j in range(i,n):
            if total[j] == n-1 or game[j] == 0:
                continue
            tmp = a[j][total[j]]
            if game[tmp-1] == 0 and a[tmp-1][total[tmp-1]] == j+1:
                total[j] += 1
                total[tmp-1] += 1
                game[j] += 1
                game[tmp-1] += 1
                count += 1
                flag = True
        if flag == False:
            break
        day += 1
    if flag == False:
        break
    i += 1

if flag == False:
    print(-1)
else:
    print(day)

Submission status: Wrong Answer

Solution code:
N = int(input())
allnodes = {(0,0)}

def order(edges):
    status = {}
    for n in allnodes:
        status[n] = None
    q = [(0, 0)]
    TMP = 1
    DONE = 2

    def visit(n):
        if status[n] == TMP:
            return False
        elif status[n] is None:
            status[n] = TMP
            for u in edges[n]:
                if visit(u) == False:
                    return False
            status[n] = DONE

        return True

    for n in allnodes:
        if visit(n) == False:
            return False
    return True

edges = {}
for a in range(1,N+1):
    l = [int(x) for x in input().split()]
    prev = (0, 0)
    for y in l:
        x = a 
        if x > y:
            x, y = y, x 
        allnodes.add((x, y))
        edges.setdefault(prev, set()).add((x, y))
        edges.setdefault((x, y), set())
        prev = x, y
#for k in edges: print(k, edges[k])
def longpath(allnodes, edges):
    q = [(0, 0)]
    D = {n:0 for n in allnodes}
    while q:
        u = q.pop()
        d = D[u]
        for v in edges[u]:
            if D[v] < d + 1:
                D[v] = d + 1
                q.append(v)
    return max(D[k] for k in D.keys())

if not order(edges):
    print(-1)

Submission status: Wrong Answer

Solution code:
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
    if y == 0:
        print(-1)
        exit()

print(min(k // 2, d - 1))

Submission status: Wrong Answer

Solution code:
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
    if y == 0:
        print(-1)
        exit()

print(d - 1)

Submission status: Wrong Answer

Solution code:
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
            print(x)
            if l[x][A[x]] * L[x] * L[i] == i + 1:
                A[i] += 1
                A[x] += 1
                L[i] = L[x] = 0
                y = 1
    if y == 0:
        print(-1)
        exit()

print(d - 1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
    if day > 3000:
        print(N*(N-1)//2)
        exit()
print(day)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
    if day > 2000:
        print(N*(N-1)//2)
        exit()
print(day)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

# how many times each player matched
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:
    print(predeq)
    postdeq = deque([])
    for i, j in predeq:
        c[i] += 1
        c[j] += 1
        if c[i] < N - 1:
            k = A[i][c[i]] # next player
            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)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
    if day > (N*(N-1)//2) // 2:
        print(N*(N-1)//2)
        exit()
print(day)

Submission status: Wrong Answer

Solution code:
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 a in A:
  if len(a) > 0:
    print(-1)
    break
else:
  print(day - 1)

Submission status: Wrong Answer

Solution code:
n=int(input());print(n*~-n//2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import deque

def main():
    N = int(input())
    M = [[]]
    for cm in range(N):
        A = list(map(int,input().split()))
        M.append(A)

    q = deque(range(1, N+1))
    day = [0] * (N+1)
    opponent = [-1] * (N+1)

    while q:
        a = q.popleft()
        if len(M[a]) > 0:
            b = M[a][0]
            if opponent[b] == a:
                day[a] = day[b] = max(day[a],day[b]) + 1
                opponent[a] = opponent[b] = -1
                M[a].pop(0)
                M[b].pop(0)
                q.append(a)
                q.append(b)
            else:
                opponent[a] = b

    answer = max(day)
    answer = answer if answer > 0 else -1
    print(answer)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import deque

def main():
    N = int(input())
    M = [[]]
    for cm in range(N):
        A = list(map(int,input().split()))
        M.append(A)

    q = deque(range(1, N+1))
    day = [0] * (N+1)
    opponent = [-1] * (N+1)

    while q:
        a = q.popleft()
        if len(M[a]) > 0:
            b = M[a][0]
            if opponent[b] == a:
                day[a] = day[b] = max(day[a],day[b]) + 1
                opponent[a] = opponent[b] = -1
                M[a].pop()
                M[b].pop()
                q.append(a)
                q.append(b)
            else:
                opponent[a] = b

    answer = max(day)
    answer = answer if answer > 0 else -1
    print(answer)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(N):
	A.append(list(map(int, input().split())))
days = 0
l = [0]*N
for _ in range(N):
	done = 0
	for i in range(N):
		if l[i] == 0:
			if len(A[i]):
				l[i] = A[i].pop(0)
			else:
				l[i] = 0
 
	if not sum(l): break
 
	for i in range(N):
		if l[l[i]-1] == i+1 and l[i] and l[l[i]-1]:
			l[l[i]-1] = 0
			l[i] = 0
			done = 1
	
	if done:
		days += 1
	else:
		print(-1)
		exit()
print(days)

Submission status: Wrong Answer

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

x=[[[] for j in range(n)] for i in range(n)]
y=[[0 for j in range(n)] for i in range(n)] #入次数

for i in range(n):
	t=[sorted([i,t-1]) for t in a[i]]
	for j in range(1,len(t)):
		k=t[j]
		y[k[0]][k[1]]+=1
	#print(t)
	for j in range(n-2):
		x[t[j][0]][t[j][1]].append(t[j+1])
#print(x)
#print(y)


from collections import deque
dis=[[1<<32 for _ in range(n)] for _ in range(n)]
que=deque([])
res=[]

for i in range(n-1):
	for j in range(i+1,n):
		if y[i][j]==0:
			que.append((i,j,1))
while que:
	tx,ty,td=que.pop()
	dis[tx][ty]=min(dis[tx][ty],td)
	for ttx,tty in x[tx][ty]:
		y[ttx][tty]-=1
		if y[ttx][tty]==0:
			que.append((ttx,tty,td+1))
	res.append([tx,ty])
#print(dis)
#print(y)

res=0
for t in dis:
	for k in t:
		if k<(1<<32):
			res=max(res,k)
j=0
for t in y:
	j+=sum(t)
if j>0:
	print(-1)
else:
	print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
a=[list(map(lambda x:int(x)-1,input().split())) for _ in range(n)]
g = [[[] for _ in range(n)] for _ in range(n)]
h=[[0]*n for _ in range(n)]
for i in range(n):
	for j in range(1,n-1):
		maf = max(i,a[i][j-1])
		mif = min(i,a[i][j-1])
		mat = max(i,a[i][j])
		mit = min(i,a[i][j])
		g[mif][maf].append([mit,mat])
		h[mit][mat] += 1

st = deque([])
sj = deque([])
for i in range(n):
	for j in range(i+1,n):
		if h[i][j]==0:
			st.append([i,j])
			sj.append([i,j])
ans=[]
while(st):
	f = st.popleft()
	ans.append(f)
	for mi,ma in g[f[0]][f[1]]:
		h[mi][ma]-=1
		if h[mi][ma] == 0:
			st.append([mi,ma])

if len(ans)!=n*(n-1)//2:
	print(-1)
	exit()

mac=0
for edge in sj:
	x=edge[0]
	y=edge[1]
	q=deque([[x,y,1]])
	used=[[False]*n for _ in range(n)]
	while(q):
		tmp=q.popleft()
		f1=tmp[0]
		f2=tmp[1]
		c=tmp[2]
		used[f1][f2]=True
		mac=max(c,mac)
		for nn in g[f1][f2]:
			if used[nn[0]][nn[1]]:
				continue
			q.append([nn[0],nn[1],c+1])
print(mac)

Submission status: Wrong Answer

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

x=[[[] for j in range(n)] for i in range(n)]
y=[[0 for j in range(n)] for i in range(n)]

for i in range(n):
	t=[sorted([i,t-1]) for t in a[i]]
	for j in range(1,len(t)):
		k=t[j]
		y[k[0]][k[1]]+=1
	#print(t)
	for j in range(n-2):
		x[t[j][0]][t[j][1]].append(t[j+1])
#print(x)
#print(y)


from collections import deque
dis=[[0 for _ in range(n)] for _ in range(n)]
que=deque([])
res=[]

for i in range(n-1):
	for j in range(i+1,n):
		if y[i][j]==0:
			que.append((i,j,1))
while que:
	tx,ty,td=que.pop()
	dis[tx][ty]=max(dis[tx][ty],td)
	for ttx,tty in x[tx][ty]:
		y[ttx][tty]-=1
		if y[ttx][tty]==0:
			que.append((ttx,tty,td+1))
	res.append([tx,ty])
#print(res,"!")
#print(dis)

res=0
for t in dis:
	res=max(max(t),res)
j=0
for t in y:
	j+=sum(t)
if j>0:
	print(-1)
else:
	print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
c=0
f = True
for i in range(N):
  A.append(list(map(int, input().split())))
idx = [0 for i in range(N)]

a = 0
cc = 0
ccc = 0

btlf = [False for i in range(N)]
btll = range(N)
m = (N*(N-1))//2
for i in range(m):
  btlf = [False for i in range(N)]
  ccc = 0
  for j in btll:
    #if idx[j] != N-1:
      a = A[j][idx[j]]
      if A[a-1][idx[a-1]]-1==j and btlf[a-1] == False and btlf[j] == False:
        #idx[a-1]+=1
        btlf[a-1] = True
        #idx[j]+=1
        btlf[j] = True
        #cc+=1
        #ccc+=1
  if cc == m:
    print(i+1)
    f = False
    break
  if ccc == 0:
    break
  btll = []
  for j in range(N):
    if btlf[j]:
      btll.append(j)
if f:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)


def LI(): return [int(x) for x in sys.stdin.readline().split()]

def main():
    N = int(input())
    X = [[] for i in range(N)]
    for i in range(N):
        for j in LI():
            X[i].append(j-1)
        X[i].reverse()

    Q = []

    def check(i):
        if X[i]:
            return
        j = X[i][-1]
        if X[j]:
            return
        if X[i][-1]==X[j][-1]:
            if i<j:
                Q.append((i,j))
            else:
                Q.append((j,i))

    for i in range(N):
        check(i)

    day = 0
    while len(Q):
        day += 1
        Q.sort()
        Q = list(set(Q))
        prevQ = Q.copy()
        Q = []
        for i,j in prevQ:
            X[i].pop()
            X[j].pop()
        for i,j in prevQ:
            check(i)
            check(j)

    for i in range(N):
        if len(X[i])>0:
            print("-1")
            return

    print(day)
    return

main()