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:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
import math
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

n=I()
t=[]
d=[]
nx=[0]*n
for i in range(n):
    a=[i-1 for i in LI()[::-1]]
    nx[i]=a.pop()
    t.append(a)
    d.append([-1]*(n))

flg=True
k=0
ans=0
MacthNum=0
while flg and MacthNum<n*(n-1)//2:
    ans+=1
    IsMatch=False
    done=[False]*n
    #print('Day',ans,IsMatch,nx)
    for i in range(n):
        if done[i] or nx[i]==[] or done[nx[i]]==True:
            continue
        if i==nx[nx[i]]:
            IsMatch=True
            MacthNum+=1
            #print('Match',i,nx[i])
            n_i=t[i].pop() if t[i] else []
            n_n_i=t[nx[i]].pop() if t[nx[i]] else []
            #print(i,nx[i],nx)
            nx[nx[i]],nx[i]=n_n_i,n_i
            if i:
                done[i]=True
            if nx[i]:
                done[nx[i]]=True
            #print('i,t,d',i,t,done,nx,n_i,n_n_i)

    ans=ans if IsMatch else -1
    flg=True if IsMatch else False

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
A = [list(map(int,input().split())) for j in range(n)]
ans = 0
while max(list(len(x) for x in A)) != 0:
  B = {}
  ans += 1
  flag = 0
  a = [x[0] for x in A if len(x) != 0]
  for c in collections.Counter(a).most_common():
    if c[1] != collections.Counter(a).most_common()[0][1]:
      break
    if len(A[c[0]-1]) != 0:
      d = A[c[0]-1][0] - 1
      e = A[d][0] - 1
      if c[0]-1 == e and c[0]-1 not in B and d not in B: 
        A[c[0]-1].pop(0)
        A[d].pop(0)
        B[c[0]-1] = 1
        B[d] = 1
        flag = 1
  if flag == 0:
      print(-1);exit()
      
print(ans)

Submission status: Wrong Answer

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

total=0
n=[0 for _ in l]
c=[False for _ in range(N)]
#end=[False for _ in range(N)]
for i in range(N):
    total+=1
    check=[False for _ in range(N)]
    #print("n:",total)
    flag=True
    for j in range(N):
        #print("j:{}".format(j))
        if n[j]==N-1 or check[j]:
            continue
        tmp=l[j][n[j]]-1
        if  check[tmp]:
            continue
        if j==l[tmp][n[tmp]]-1:
            flag=False
            n[j]+=1
            n[tmp]+=1
            check[j]=True
            check[tmp]=True
            """
            if n[j]==N-1:
                end[j]=True
            if n[tmp]==N-1:
                end[tmp]=True
            """
    if flag:
        print(-1)
        exit()
print(total)

Submission status: Wrong Answer

Solution code:
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0 for i in[0]*n];d=1;k=n*(n-1)
while sum(a)<k and 0<d<9*n:
 L=[0 for i in[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
 d*=y
print([k//2,d-1][d<9*n])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
import time
start=time.time()
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]:
			aite=data[i][0]
			if data[aite-1][0]==i+1:
				if taisenzumi[i]:break
				if taisenzumi[aite-1]:break				
				data[i].popleft()
				data[aite-1].popleft()
				taisenzumi[aite-1]=1
				taisenzumi[i]=1
				last-=2
				flag=0
			else:continue
	if flag:
		break
	if time.time()-start>1.9:
		print(1000*999//2)
		exit()
else:
	print(count)
	exit()
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
import time
start=time.time()
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]:
			aite=data[i][0]
			if data[aite-1][0]==i+1:
				if taisenzumi[i]:break
				if taisenzumi[aite-1]:break				
				data[i].popleft()
				data[aite-1].popleft()
				taisenzumi[aite-1]=1
				taisenzumi[i]=1
				last-=2
				flag=0
			else:continue
	if flag:
		break
	if time.time()-start>1.8:
		print(1000*999//2)
		exit()
else:
	print(count)
	exit()
print(-1)

Submission status: Wrong Answer

Solution code:
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 match > 400000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
N = int(input())
e = dd(list)
for i in range(1, N + 1):
  e[i] = list(map(int, input().split()))
vis = [0] * (N + 1)
day = 1
#print(e)
while day <= N * (N - 1) // 2 and sum(vis) < N * (N - 1):
  for i in range(1, N + 1):
    if vis[i] >= N - 1:
      continue
    j = e[i][vis[i]]
    #print(i, j, vis[i], vis[e[j][vis[j]]])
    #print(vis)
    if i == e[j][vis[j]]:
      vis[i] += 1
      vis[j] += 1
    #print(vis)
  day += 1
print(day) if sum(vis) == N * (N - 1) else print(-1)

Submission status: Wrong Answer

Solution code:
import sys


def topological_check(roots, out_links, in_count):
    depth = [0] * match_count
    for r in roots:
        depth[r] = 1
    q = roots
    while q:
        v = q.pop()
        d = depth[v] + 1
        for u in out_links[v]:
            in_count[u] -= 1
            if in_count[u] == 0:
                depth[u] = d
                q.add(u)
    if any(in_count):
        return 0
    return max(depth)


n = int(input())
match_count = n * (n - 1) // 2

offsets = [0]
tmp = -2
for i in range(1, n + 1):
    offsets.append(tmp)
    tmp += n - i - 1

roots = set()
in_links = [set() for _ in range(match_count)]
out_links = [set() for _ in range(match_count)]

for i, line in enumerate(sys.stdin, start=1):
    aaa = list(map(int, line.split()))
    j = aaa[0]
    prev = offsets[i] + j if i < j else offsets[j] + i
    roots.add(prev)

    for j in aaa[1:]:
        key = offsets[i] + j if i < j else offsets[j] + i
        out_links[prev].add(key)
        in_links[key].add(prev)
        prev = key

in_count = list(map(len, in_links))
roots = {r for r in roots if in_count[r] == 0}

if not roots:
    print(-1)
    exit()

print(topological_check(roots, out_links, in_count))

Submission status: Wrong Answer

Solution code:
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
while c!=n*(n-1)//2 and d<=10**4:
  L=[0 for i in[0]*n]
  for i in range(n):
    if L[i]==0 and a[i]!=n-1:
      x=l[i][a[i]]
      if l[x-1][a[x-1]]-1==i and L[x-1]==0:
        a[i]+=1;a[x-1]+=1;L[i]=1;L[x-1]=1;c+=1
  d+=1
print(n*(n-1)//2) if d>10**4 else print(d)

Submission status: Wrong Answer

Solution code:
import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
opo = [1 for i in range(n)]
cl = opo
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = opo

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A = [deque(list(map(int, input().split()))) for _ in range(N)]
ans = 0
t = 0
z = 0
Atmp = []
for i in range(10**7):
    for k in range(N):
        if A[k] != deque([]):
            if A[k][0] == 0:
                A[k].popleft()
            else:
                z += 1
        else:
            t += 1
    if t == N:
        break
    if t+z == N and i > 100:
        ans = 0
        break
    t = 0
    for j in range(N):
        if A[j]:
            tmp = A[j][0]
        else:
            continue
        if tmp-1 > j and A[tmp-1][0] -1 == j:
            A[j][0] = 0
            A[tmp-1][0] = 0
    ans += 1
print(ans-1)

Submission status: Wrong Answer

Solution code:
n = int(input())

a = [[0] for _ in range(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
used = [False]*n

head = 0
day = 0

for i in range(min(n*(n-1)//2,10**3)):
    if t == [-1]*n:
        break
    while True:
        if used[head] == False:
            used[head] = True
            if used[t[head]] == False:
                if t[t[head]] == head:
                    used[t[head]] = True
                    l[head] += 1
                    l[t[head]] += 1
                    t[t[head]] = a[t[head]][l[t[head]]]
                    t[head] = a[head][l[head]]
                    head = (head + 1)%n    
                else:
                    head = (head + 1)%n
        elif used[head] == True:
            head = (head + 1)%n
        if used == [True]*n:
            day += 1
            used = [False]*n
            break

if t != [-1]*n:
    print(-1)
    exit()

print(day)

Submission status: Wrong Answer

Solution code:
import collections as cl,sys
input = sys.stdin.readline
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]
lde = len(de)
while de:
    kkk = de.pop()
    lde -= 1
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if lde == 0:
            break
        de.append([-1,-1])
        lde += 1
        co += 1
        cl = [1 for i in range(n)]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0  and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
            lde += 1
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
                lde += 1
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])
                lde += 1


print(co)

Submission status: Wrong Answer

Solution code:
import collections as cl,sys
input = sys.stdin.readline
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]
lde = len(de)
while de:
    kkk = de.pop()
    lde -= 1
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if lde == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
            lde += 1
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
                lde += 1
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])
                lde += 1


print(co)

Submission status: Wrong Answer

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 and sLst[a[j][0] - 1] == 0:
                if a[a[j][0] - 1][0] == j + 1:
                    sLst[a[j][0] - 1] = a[a[j][0] - 1].pop(0)
                    sLst[j] = a[j].pop(0)
                    tmp += 1
                    total -= 1
    if total == 0:
        ans += 1
        break

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

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = [[int(x)-1 for x in input().split()] for _ in range(N)]
cnt = 0
g = [-1] * N
for u, to_lst in enumerate(A_list):
    g[u] = to_lst.pop(0)
q = []
while(1):
    need_break = 1
    loop = 1
    for i, to in q:
        if (len(A_list[i])):
            g[i] = A_list[i].pop()
        if (len(A_list[to])):
            g[to] = A_list[to].pop()
    q = []
    for i, to in enumerate(g):
        need_break *= (to == -1)
        if (to != -1 and i == g[to]):
            g[i] = -1
            g[to] = -1
            loop = 0
            q.append([i, to])
    if (need_break):
        break
    if (loop):
        print(-1)
        exit()
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()

INF = 10 ** 18
MOD = 10 ** 9 + 7
def conv(n,a,b):
    return 10000 * a + b

def main():
    N = II()
    A = [[] for _ in range(N)]
    for i in range(N):
        A[i] = [a-1 for a in LI()]

    from collections import defaultdict
    outs = defaultdict(list)
    ins = defaultdict(int)
    edge_list = []
    for i in range(N):
        for j in range(N - 2):
            a = A[i][j]
            b = A[i][j+1]
            prev = (min(i, a), max(i, a))
            next = (min(i, b), max(i, b))
            edge_list.append((conv(N, prev[0], prev[1]), conv(N, next[0], next[1])))

    for fr, to in edge_list:
        outs[fr].append(to)
        ins[to] += 1

    from collections import deque
    q = deque()
    for i in range(N):
        j = A[i][0]
        key = conv(N, i, j)
        if i < j and ins[key] == 0:
            q.append([key, 0])

    if not q:
        print(-1)
        return

    res = []
    depth_max = 0
    while q:
        v1, depth = q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append([v2, depth + 1])
                depth_max = max(depth_max, depth + 1)
    if q:
        print(-1)
        return
    else:
        print(depth_max + 1)
        return


main()

Submission status: Wrong Answer

Solution code:
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 ans==0 else ans)

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 LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


def conv(n,a,b):
    return a*(2*n-a-1)//2+b-a-1

def main(): 
    N = II()
    # A = [[] for _ in range(N)]
    # for i in range(N):
    #     A[i] = LI()

    # print(A)
    # return

    from collections import defaultdict
    outs = defaultdict(list)
    ins = defaultdict(int)
    for i in range(N):
        # prev_v = (i+1, A[i][0]) if i+1 < A[i][0] else (A[i][0], i+1)
        a = LI()
        for j in range(1,N-1):
            # prev_v = (i+1, A[i][j-1]) if i+1 < A[i][j-1] else (A[i][j-1], i+1)
            # next_v = (i+1, A[i][j]) if (i+1 < A[i][j]) else (A[i][j] , i+1)
            # prev_v = conv(N, prev_v[0], prev_v[1])
            # next_v = conv(N, next_v[0], next_v[1])
            prev_v = (min(i+1, a[j-1]), max(i+1, a[j-1]))
            next_v = (min(i+1, a[j]), max(i+1, a[j]))
            prev_v = conv(N, prev_v[0]-1, prev_v[1]-1)
            next_v = conv(N, next_v[0]-1, next_v[1]-1)
            outs[prev_v].append(next_v)
            ins[next_v] += 1

    # print(outs, ins)
    # return

    from collections import deque
    q = deque()
    for i in range(1, N+1):
        for j in range(1, N+1):
        # j = A[i-1][0]
            if i < j and ins[conv(N, i-1, j-1)] == 0:
                q.append([conv(N, i-1, j-1), 0])

    if not q:
        print(-1)
        return

    # q = deque(v1 for v1 in range(1, N+1) if ins[v1] == 0)
    res = []
    depth_max = 0
    while q:
        v1, depth = q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append([v2, depth+1])
                depth_max = max(depth_max, depth+1)
    if q:
        print(-1)
        return
    else:
        print(depth_max+1)
        return


main()

Submission status: Wrong Answer

Solution code:
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=1
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 ans==0 else ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
for i in range(n):
  	a = list(map(int,input().split()))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()

INF = 10 ** 18
MOD = 10 ** 9 + 7
def conv(n,a,b):
    return a*(2*n-a-1)//2+b-a-1
def main():
    N = II()
    A = [[] for _ in range(N)]
    for i in range(N):
        A[i] = [a-1 for a in LI()]

    from collections import defaultdict
    outs = defaultdict(list)
    ins = defaultdict(int)
    edge_list = []
    for i in range(N):
        for j in range(N - 2):
            a = A[i][j]
            b = A[i][j+1]
            prev = (min(i, a), max(i, a))
            next = (min(i, b), max(i, b))
            edge_list.append((conv(N, prev[0], prev[1]), conv(N, next[0], next[1])))

    for fr, to in edge_list:
        outs[fr].append(to)
        ins[to] += 1

    from collections import deque
    q = deque()
    for i in range(N):
        j = A[i][0]
        key = conv(N, i, j)
        if i < j and ins[key] == 0:
            q.append([key, 0])

    if not q:
        print(-1)
        return

    res = []
    depth_max = 0
    while q:
        v1, depth = q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append([v2, depth + 1])
                depth_max = max(depth_max, depth + 1)
    if q:
        print(-1)
        return
    else:
        print(depth_max + 1)
        return


main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()

INF = 10 ** 18
MOD = 10 ** 9 + 7

def main():
    N = II()
    A = [[] for _ in range(N)]
    for i in range(N):
        A[i] = [a-1 for a in LI()]

    from collections import defaultdict
    outs = defaultdict(list)
    ins = defaultdict(int)
    edge_list = []
    for i in range(N):
        for j in range(N - 2):
            a = A[i][j]
            b = A[i][j+1]
            prev = (min(i, a), max(i, a))
            next = (min(i, b), max(i, b))
            edge_list.append((prev, next))

    for fr, to in edge_list:
        outs[fr].append(to)
        ins[to] += 1

    from collections import deque
    q = deque()
    for i in range(N):
        j = A[i][0]
        if i < j and ins[(i, j)] == 0:
            q.append([(i, j), 0])

    if not q:
        print(-1)
        return

    res = []
    depth_max = 0
    while q:
        v1, depth = q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append([v2, depth + 1])
                depth_max = max(depth_max, depth + 1)
    if q:
        print(-1)
        return
    else:
        print(depth_max + 1)
        return


main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
debug = True
#debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

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


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


def LF(): return [float(x) for x in sys.stdin.readline().split()]


def LS(): return sys.stdin.readline().split()


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


def SI(): return sys.stdin.readline().strip()


INF = 10 ** 18
MOD = 10 ** 9 + 7


def main():
    N = II()
    A = [[] for _ in range(N)]
    for i in range(N):
        A[i] = [a-1 for a in LI()]

    from collections import defaultdict
    outs = defaultdict(list)
    ins = defaultdict(int)
    edge_list = []
    for i in range(N):
        for j in range(N - 2):
            a = A[i][j]
            b = A[i][j+1]
            prev = (min(i, a), max(i, a))
            next = (min(i, b), max(i, b))
            edge_list.append((prev, next))

    dprint(edge_list)
    for fr, to in edge_list:
        outs[fr].append(to)
        ins[to] += 1

    from collections import deque
    q = deque()
    for i in range(N):
        j = A[i][0]
        if i < j and ins[(i, j)] == 0:
            q.append([(i, j), 0])

    if not q:
        print(-1)
        return
    dprint(q)
    dprint(outs)
    dprint(ins)
    res = []
    depth_max = 0
    while q:
        v1, depth = q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append([v2, depth + 1])
                depth_max = max(depth_max, depth + 1)
    if q:
        print(-1)
        return
    else:
        print(depth_max + 1)
        return


main()

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
today = []
ans = 1

while True:
    match = 0
    empty = 0
    for p in range(n):
        if not a[p]:
            empty += 1
            if empty == n-1:
                print(ans)
                sys.exit()
            continue
        o = a[p][0] - 1
        if p == a[o][0] - 1:
            match += 1
            a[p].pop(0)
            a[o].pop(0)
            if (p in today) or (o in today):
                today = [p, o]
                ans += 1
            else:
                today += [p, o]
        if p == n-1 and match == 0:
            print(-1)
            sys.exit()

Submission status: Wrong Answer

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

while True:
    today = []
    match = 0
    empty = 0
    ans += 1
    for p in range(n):
        if p in today:
            continue
        if not a[p]:
            empty += 1
            if empty == n-1:
                print(ans)
                sys.exit()
            continue
        o = a[p][0] - 1
        if p == a[o][0] - 1:
            match += 1
            a[p].pop(0)
            a[o].pop(0)
            today += [p, o]
        if p == n-1 and match == 0:
            print(-1)
            sys.exit()

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 LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


def conv(n,a,b):
    return a*(2*n-a)//2+b-a

def main(): 
    N = II()
    # A = [[] for _ in range(N)]
    # for i in range(N):
    #     A[i] = LI()

    # print(A)
    # return

    from collections import defaultdict
    outs = defaultdict(list)
    ins = defaultdict(int)
    for i in range(N):
        # prev_v = (i+1, A[i][0]) if i+1 < A[i][0] else (A[i][0], i+1)
        a = LI()
        for j in range(1,N-1):
            # prev_v = (i+1, A[i][j-1]) if i+1 < A[i][j-1] else (A[i][j-1], i+1)
            # next_v = (i+1, A[i][j]) if (i+1 < A[i][j]) else (A[i][j] , i+1)
            # prev_v = conv(N, prev_v[0], prev_v[1])
            # next_v = conv(N, next_v[0], next_v[1])
            prev_v = (min(i+1, a[j-1]), max(i+1, a[j-1]))
            next_v = (min(i+1, a[j]), max(i+1, a[j]))
            outs[prev_v].append(next_v)
            ins[next_v] += 1

    # print(outs, ins)
    # return

    from collections import deque
    q = deque()
    for i in range(1, N+1):
        for j in range(1, N+1):
        # j = A[i-1][0]
            if i < j and ins[(i, j)] == 0:
                q.append([(i, j), 0])

    if not q:
        print(-1)
        return

    # q = deque(v1 for v1 in range(1, N+1) if ins[v1] == 0)
    res = []
    depth_max = 0
    while q:
        v1, depth = q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append([v2, depth+1])
                depth_max = max(depth_max, depth+1)
    if q:
        print(-1)
        return
    else:
        print(depth_max+1)
        return


main()