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:
import sys
import bisect
import math
import itertools
from collections import deque
import copy

# \n
def input():
    return sys.stdin.readline().rstrip()


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

    L = [[] for _ in range(N + 1)]

    for j in range(N):
        a = list(map(int, input().split()))
        L[j + 1] = deque(a)


    k =0

    current_revise =set(range(N+1))
    while k<50000: # １日分の作業

        pre_revise =copy.copy(current_revise)
        current_revise =set()

        for i in pre_revise: #一人分の作業
            if not L[i]:
                continue
            can = L[i][0]
            if L[can][0] == i and i not in current_revise and can not in current_revise:
                L[i].popleft()
                L[can].popleft()

                current_revise.add(i)
                current_revise.add(can)
        k += 1

        if len(current_revise)==0:
            break


    for i in range(N + 1):
        if len(L[i])>0:
            print(-1)
            exit()

    print(k-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import math
import itertools
from collections import deque
import copy

# \n
def input():
    return sys.stdin.readline().rstrip()


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

    L = [[] for _ in range(N + 1)]

    for j in range(N):
        a = list(map(int, input().split()))
        L[j + 1] = deque(a)

    f_original = [False] * (N + 1)
    f = [False] * (N + 1)
    k =0

    pre_revise =set(range(N+1))
    current_revise =set(range(N+1))
    while k<50000: # １日分の作業

        f =[False] * (N + 1)
        pre_revise =copy.copy(current_revise)
        current_revise =set()

        for i in pre_revise: #一人分の作業
            if not L[i]:
                continue
            can = L[i][0]
            if L[can][0] == i and f[can] is False and f[i] is False:
                L[i].popleft()
                L[can].popleft()
                f[i] = True
                f[can] = True
                current_revise.add(i)
                current_revise.add(can)
        k += 1
        
        if f == f_original:
            break

    for i in range(N + 1):
        if len(L[i])>0:
            print(-1)
            exit()

    print(k-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
graph = [[[] for _ in range(n+1)] for _ in range(n+1)]
indeg = [[0] * (n+1) for _ in range(n+1)]
for i in range(1, n+1):
    a = tuple(map(int, input().split()))
    for j, v in enumerate(a):
        if j == n-2:
            continue
        tmp = (min(i, a[j+1]), max(i, a[j+1]))
        indeg[tmp[0]][tmp[1]] += 1
        if i < v:
            graph[i][v].append(tmp)
        else:
            graph[v][i].append(tmp)

q = deque([])
for i in range(1, n+1):
    for j in range(i+1, n+1):
        if indeg[i][j] == 0:
            q.append((i, j, 1))

ans = -1
while q:
    x, y, day = q.popleft()
    # print(x, y, day)
    ans = max(ans, day)
    for p, r in graph[x][y]:
        if indeg[p][r] == 0:
            continue
        indeg[p][r] -= 1
        if indeg[p][r] == 0:
            q.append((p, r, day+1))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
graph = [[[] for _ in range(n+1)] for _ in range(n+1)]
indeg = [[0] * (n+1) for _ in range(n+1)]
for i in range(1, n+1):
    a = tuple(map(int, input().split()))
    for j, v in enumerate(a):
        if j == n-2:
            continue
        tmp = (min(i, a[j+1]), max(i, a[j+1]))
        indeg[tmp[0]][tmp[1]] += 1
        if i < v:
            graph[i][v].append(tmp)
        else:
            graph[v][i].append(tmp)

q = deque([])
for i in range(1, n+1):
    for j in range(i+1, n+1):
        if indeg[i][j] == 0:
            q.append((i, j, 1))

ans = -1
while q:
    x, y, day = q.popleft()
    print(x, y, day)
    ans = max(ans, day)
    for p, r in graph[x][y]:
        if indeg[p][r] == 0:
            continue
        indeg[p][r] -= 1
        if indeg[p][r] == 0:
            q.append((p, r, day+1))

print(ans)

Submission status: Wrong Answer

Solution code:
"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    N = int(input())

    A = [[0]*(N)]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))
    
    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = {i:{} for i in range(1,N+1)}
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j

    #edges[(i,j)] => (i,j)の試合が終わらないと開始できない試合＝iにとってjの次の対戦相手の試合＆jにとってiの次の対戦相手との試合
    edges = {}
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            match = (i,j)
            edges[match] = []
            if reverseMemo[i][j] != N-1:
                nx = A[i][reverseMemo[i][j]+1]
                edges[match].append((min(i,nx),max(i,nx)))
            if reverseMemo[j][i] != N-1:
                nx = A[j][reverseMemo[j][i]+1]
                edges[match].append((min(j,nx),max(j,nx)))
    
    #edges[(i,j)] => (i,j)の試合を開始する前に消化しなくては行けない試合＝iにとってjの前の対戦相手との試合＆jにとってiの前の対戦相手との試合
    reverseEdges = {}
    for k,vs in edges.items():
        if k not in reverseEdges:
            reverseEdges[k] = []
        for v in vs:
            if v not in reverseEdges:
                reverseEdges[v] = []
            reverseEdges[v].append(k)
    
    del reverseMemo
    del A
    
    que = []
    for k,vs in reverseEdges.items():
        if len(vs) == 0:
            que.append((k,1))
    que = deque(que)
    endMatch = set()

    if not que:
        print(-1)
        exit()
    
    cnt = 0
    ans = 0
    while que:
        cnt += 1
        if cnt > N*N:
            print(-1)
            exit()
        match,day = que.popleft()
        for preMatch in reverseEdges[match]:
            if preMatch not in endMatch:
                break
        else:
            endMatch.add(match)
            ans = max(ans,day)
            for nxMatch in edges[match]:
                que.append((nxMatch,day+1))
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
import numpy as np

n=int(input())
dp=[[-1]*n for i in range(n)]

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

dp=np.array(dp)

ans=0
while True:
  g=np.argwhere(dp==0)
  #print(dp)
  if len(g)==0:
    break
  else:
    t=[]
    ans+=1
    flg=False
    for i,j in g:
      if i<j and i not in t and j not in t:
        #print(i,j)
        flg=True
        t.append(i)
        t.append(j)
        dp[i]-=1
        dp[j]-=1
    if flg:
      continue
    else:
      print(-1)
      exit(0)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n=int(input())
dp=[[-1]*n for i in range(n)]

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

dp=np.array(dp)

ans=0
while True and ans<10:
  g=np.argwhere(dp==0)
  #print(dp)
  if len(g)==0:
    break
  else:
    t=[]
    ans+=1
    flg=False
    for i,j in g:
      if i<j and i not in t and j not in t:
        #print(i,j)
        flg=True
        t.append(i)
        t.append(j)
        dp[i]-=1
        dp[j]-=1
    if flg:
      continue
    else:
      print(-1)
      exit(0)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(20000)

N = int(input())
A = [[0]*(N)]
for _ in range(N):
    A.append([0]+list(map(int,input().split())))

#選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
reverseMemo = {i:{} for i in range(1,N+1)}
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        reverseMemo[i][a] = j

dp = [[0]+[None]*N for _ in range(N+1)]

def f(i,j,cnt):
    #iとjの試合が最速でいつできるかを返す。
    if cnt > N:
        print(-1)
        exit()
    if dp[i][j] == None and dp[j][i] == None:
        #iの一つ前の試合がいつおわるかを調べる。
        pre = A[i][reverseMemo[i][j]-1]
        tmp1 = f(i,pre,cnt+1)
        
        #jの一つ前の試合がいつおわるかを調べる。
        pre = A[j][reverseMemo[j][i]-1]
        tmp2 = f(j,pre,cnt+1)

        dp[i][j] = max(tmp1,tmp2)+1

    elif dp[i][j] == None and dp[j][i] != None:
        dp[i][j] = dp[j][i]
    elif dp[i][j] != None and dp[j][i] != None:
        dp[j][i] = dp[i][j]
    return dp[i][j]

ans = 0
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        ans = max(ans,f(i,a,0))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
day = 0
while True:
    day += 1
    flag = True
    Done = [False] * N
    for i, a in enumerate(A):
        if len(a) == 0:
            continue
        if Done[i]:
            continue
        x = a[-1] - 1
        if A[x] and A[x][-1] - 1 == i:
            A[i].pop()
            A[x].pop()
            Done[i] = True
            Done[x] = True
            flag = False
    if flag:
        break
F = False
for a in A:
    if len(a) != 0:
        F = True
        break
if F:
    print(-1)
else:
    print(day)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(now):
  res=day[now]
  if vis[now]:
    if res==-1:return -1
    else:return res
  #res=1
  vis[now]=1
  for to in d[now]:
    r=dfs(to)
    if r==-1:return -1
    res=max(res,r+1)
  day[now]=res
  return res
n=int(input())
INF=10**18
c=[]
for i in range(n):
  for j in range(i+1,n):
    c+=[(i,j)]
d=dict(zip(c,[[] for _ in range(n*(n-1)//2)]))
s=[]
for i in range(n):
  a=list(map(int,input().split()))
  if i<a[0]-1:b=(i,a[0]-1)
  else:b=(a[0]-1,i)
  s+=[b]
  for j in a[1:]:
    j-=1
    if i<j:
      d[b]+=[(i,j)]
      b=(i,j)
    else:
      d[b]+=[(j,i)]
      b=(j,i)
vis=dict(zip(c,[0]*(n*(n-1)//2)))
day=dict(zip(c,[-1]*(n*(n-1)//2)))
ans=0
for i in s:
  di=dfs(i)
  if di==-1:
    print(-1)
    exit()
  ans=max(ans,di)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(now):
  res=day[now]
  if vis[now]:
    if res==-1:return -1
    else:return res
  vis[now]=1
  for to in d[now]:
    r=dfs(to)
    if r==-1:return -1
    res=max(res,r+1)
  day[now]=res
  return res
n=int(input())
INF=10**18
c=[]
for i in range(n):
  for j in range(i+1,n):
    c+=[(i,j)]
d=dict(zip(c,[[] for _ in range(n*(n-1)//2)]))
s=[]
for i in range(n):
  a=list(map(int,input().split()))
  if i<a[0]-1:b=(i,a[0]-1)
  else:b=(a[0]-1,i)
  s+=[b]
  for j in a[1:]:
    j-=1
    if i<j:
      d[b]+=[(i,j)]
      b=(i,j)
    else:
      d[b]+=[(j,i)]
      b=(j,i)
vis=dict(zip(c,[0]*(n*(n-1)//2)))
day=dict(zip(c,[-1]*(n*(n-1)//2)))
ans=0
for i in s:
  di=dfs(i)
  if di==-1:
    print(-1)
    exit()
  ans=max(ans,di)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
G = {}
for i in range(1,N+1):
    a = list(map(int,input().split()))
    i1 = i
    i2 = a[0]
    if i1>i2:
        i1,i2 = i2,i1
    if (i1,i2) not in G:
        G[(i1,i2)] = [0,[]]
    for j in range(1,N-1):
        i1 = i
        i2 = a[j-1]
        i3 = i
        i4 = a[j]
        if i1>i2:
            i1,i2 = i2,i1
        if i3>i4:
            i3,i4 = i4,i3
        G[(i1,i2)][1].append((i3,i4))
        if (i3,i4) not in G:
            G[(i3,i4)] = [0,[]]
        G[(i3,i4)][0] += 1

que = deque([])
hist = {}
for a in G:
    hist[a] = 0
flag = 0
for a in G:
    if G[a][0]==0:
        que.append((a,1))
        hist[a] = 1
if len(que)==0:
    flag = 1
if flag==0:
    cnt = 0
    while que:
        a,d = que.popleft()
        for b in G[a][1]:
            if hist[b]==1:
                flag = 1
                break
            G[b][0] -= 1
            if G[b][0]==0:
                que.append((b,d+1))
                cnt = d+1
                hist[b] = 1
        if flag==1:break
if flag==1:
    print(-1)
else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    idx = [0] * N
    D = [[-1] * (N) for _ in range(N)]
    for j in range(N):
        D[j][0] = 0
    while True:
        f = True
        for i in range(N):
            if idx[i] >= N - 1: continue
            m = A[i][idx[i]]
            if A[m][idx[m]] == i:
                d = max(D[i][idx[i]], D[m][idx[m]])
                idx[i] += 1
                idx[m] += 1
                D[i][idx[i]] = d + 1
                D[m][idx[m]] = d + 1
                f = False
        if f: break
    ans = -1
    for i in range(N):
        ans = max(ans, D[i][N - 2])
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(N)]
    main(N, A)

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    idx = [0] * N
    D = [[-1] * (N) for _ in range(N)]
    for j in range(N):
        D[j][0] = 0
    while True:
        f = True
        for i in range(N):
            if idx[i] >= N - 1: continue
            m = A[i][idx[i]]
            if A[m][idx[m]] == i:
                d = max(D[i][idx[i]], A[m][idx[m]])
                idx[i] += 1
                idx[m] += 1
                D[i][idx[i]] = d + 1
                D[m][idx[m]] = d + 1
                f = False
        if f: break
    ans = -1
    for i in range(N):
        ans = max(ans, D[i][N - 2])
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(N)]
    main(N, A)

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
sys.setrecursionlimit(10**6)

n = ni()
A2 = []
tree = collections.defaultdict(list)
go=collections.defaultdict(lambda:False)
back=collections.defaultdict(lambda:False)
start = []
for i in range(n):
    A1 = lma()
    pu,pv = i,A1[0]-1
    if pu>pv:pu,pv=pv,pu
    start.append((pu,pv))
    for j in range(1,n-1):
        u,v = i,A1[j]-1
        if u>v:u,v=v,u
        tree[(pu,pv)].append((u,v))
        pu,pv=u,v
        start.append((pu,pv))
#print(tree)
def dfs(s,cnt):
    ret=cnt
    go[s]=True
    for nu,nv in tree[s]:
        if not go[(nu,nv)]:
            ret = max(dfs((nu,nv),cnt+1),ret)
        else:
            if not back[(nu,nv)]:
                print(-1)
                exit()
    back[s]=True
    return ret
ans = 0
for s in start:
    if not go[s]:
        ans = max(ans,dfs(s,1))
print(ans)

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
sys.setrecursionlimit(10**6)

n = ni()
A2 = []
tree = collections.defaultdict(list)
go=collections.defaultdict(lambda:False)
back=collections.defaultdict(lambda:False)
start = []
for i in range(n):
    A1 = lma()
    pu,pv = i,A1[0]-1
    if pu>pv:pu,pv=pv,pu
    start.append((pu,pv))
    for j in range(1,n-1):
        u,v = i,A1[j]-1
        if u>v:u,v=v,u
        tree[(pu,pv)].append((u,v))
        pu,pv=u,v
#print(tree)
def dfs(s,cnt):
    ret=cnt
    go[s]=True
    for nu,nv in tree[s]:
        if not go[(nu,nv)]:
            ret = max(dfs((nu,nv),cnt+1),ret)
        else:
            if not back[(nu,nv)]:
                print(-1)
                exit()
    back[s]=True
    return ret
ans = 0
for s in start:
    if not go[s]:
        ans = max(ans,dfs(s,1))
print(ans)

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
sys.setrecursionlimit(10**6)
n = ni()
A2 = []
tree = collections.defaultdict(list)
visited=collections.defaultdict(lambda:False)
start = []
for i in range(n):
    A1 = lma()
    pu,pv = i,A1[0]-1
    if pu>pv:pu,pv=pv,pu
    start.append((pu,pv))
    for j in range(1,n-1):
        u,v = i,A1[j]-1
        if u>v:u,v=v,u
        tree[(pu,pv)].append((u,v))
        pu,pv=u,v

def dfs(u,v,cnt):
    ret=cnt
    for nu,nv in tree[(u,v)]:
        if visited[(nu,nv)]:
            print(-1)
            exit()
        visited[(nu,nv)]=True
        ret = max(dfs(nu,nv,cnt+1),ret)
    return ret
ans = 0
for u,v in start:
    if not visited[(u,v)]:
        visited[(u,v)]=True
        ans = max(ans,dfs(u,v,1))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

cnt = 0
while True:
    can_flg = False
    quit_flg = True
    done_flg = [False]*N

    for i in range(N):
        flg = False
        if A[i]:
            can_flg = True
            v = A[i].popleft()
            if v > i and A[v]:
                u = A[v].popleft()
                if u != i or done_flg[v]:
                    A[v].appendleft(u)
                else:
                    flg = True
                    quit_flg = False
                    done_flg[i] = True
                    done_flg[v] = True
            if not flg:
                A[i].appendleft(v)

    if not can_flg:
        break
    
    cnt += 1

    if quit_flg:
        cnt = -1
        break

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

cnt = 0
while True:
    can_flg = False
    quit_flg = True
    
    for i in range(N):
        flg = False
        if A[i]:
            can_flg = True
            v = A[i].popleft()
            if v > i and A[v]:
                u = A[v].popleft()
                if u != i:
                    A[v].appendleft(u)
                else:
                    flg = True
                    quit_flg = False
            if not flg:
                A[i].appendleft(v)
    
    cnt += 1

    if not can_flg:
        break

    if quit_flg:
        cnt = -1
        break

print(cnt)

Submission status: Wrong Answer

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

es = [[[] for j in range(i)] for i in range(N)]
indeg = [[0]*i for i in range(N)]
for i,row in enumerate(A):
    for x,y in zip(row,row[1:]):
        x,y = x-1,y-1
        a0,b0 = (i,x) if i>x else (x,i)
        a1,b1 = (i,y) if i>y else (y,i)
        es[a0][b0].append((a1,b1))
        indeg[a1][b1] += 1

from collections import deque
q = deque()
for i in range(N):
    for j in range(i):
        if indeg[i][j] == 0:
            q.append((i,j,1))

ans = -1
used = set()
while q:
    a0,b0,d = q.popleft()
    ans = max(ans,d)
    used.add((a0,b0))
    for a1,b1 in es[a0][b0]:
        indeg[a1][b1] -= 1
        if indeg[a1][b1] == 0:
            if (a1,b1) in used:
                print(-1)
                exit()
            q.append((a1,b1,d+1))
            used.add((a1,b1))
print(ans)

Submission status: Wrong Answer

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

es = [[[] for j in range(i)] for i in range(N)]
indeg = [[0]*i for i in range(N)]
for i,row in enumerate(A):
    for x,y in zip(row,row[1:]):
        x,y = x-1,y-1
        a0,b0 = (i,x) if i>x else (x,i)
        a1,b1 = (i,y) if i>y else (y,i)
        es[a0][b0].append((a1,b1))
        indeg[a1][b1] += 1

from collections import deque
q = deque()
used = set()
for i in range(N):
    for j in range(i):
        if indeg[i][j] == 0:
            q.append((i,j,1))
            used.add((i,j))

ans = -1
while q:
    a0,b0,d = q.popleft()
    ans = max(ans,d)
    for a1,b1 in es[a0][b0]:
        indeg[a1][b1] -= 1
        if indeg[a1][b1] == 0:
            if (a1,b1) in used:
                print(-1)
                exit()
            q.append((a1,b1,d+1))
            used.add((a1,b1))
print(ans)

Submission status: Wrong Answer

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

es = [[[] for j in range(i)] for i in range(N)]
indeg = [[0]*i for i in range(N)]
for i,row in enumerate(A):
    for x,y in zip(row,row[1:]):
        x,y = x-1,y-1
        a0,b0 = (i,x) if i>x else (x,i)
        a1,b1 = (i,y) if i>y else (y,i)
        es[a0][b0].append((a1,b1))
        indeg[a1][b1] += 1

from collections import deque
q = deque()
for i in range(N):
    for j in range(i):
        if indeg[i][j] == 0:
            q.append((i,j,1))

ans = -1
while q:
    a0,b0,d = q.popleft()
    ans = max(ans,d)
    for a1,b1 in es[a0][b0]:
        indeg[a1][b1] -= 1
        if indeg[a1][b1] == 0:
            q.append((a1,b1,d+1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
N = n*(n-1)//2
index = {}
ind = 0
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
    for j in range(i+1,n):
        index[i,j] = ind
        index[j,i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i,a[i][j]]
        v = index[i,a[i][j+1]]
        ns[u].append(v)
### サイクル検出 cycle detection
seen = [False] * N
done = [False] * N
vals = [None] * N
def dfs(u):
    s = [u]
    seen[u] = True
    while s:
        u = s.pop()
        if u>=0:
            s.append(~u)
            for v in ns[u]:
                if done[v]:
                    continue
                elif not seen[v]:
                    seen[v] = True
                    s.append(v)
                else:
                    # 閉路発見
                    return True
        else:
            u = ~u
            done[u] = True
            # ここに帰りがけ処理を書く
            val = 0
            for v in ns[u]:
                val = max(val, vals[v]+1)
            vals[u] = val
    return False

ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u)
    if pos:
        print(-1)
        break
else:
    print(max(vals)+1)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
N = n*(n-1)//2
index = {}
ind = 0
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
    for j in range(i+1,n):
        index[i,j] = ind
        index[j,i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i,a[i][j]]
        v = index[i,a[i][j+1]]
        ns[u].append(v)
### サイクル検出 cycle detection
seen = [False] * N
done = [False] * N
hist = []
def dfs(u, pos):
    # uからdfs
    seen[u] = True
    hist.append(u)
    ans = -float("inf")
    for v in ns[u]:
        if done[v]:
            continue
        elif seen[v]:
            # サイクルを検出
            pos = v
            return pos,None
        else:
            pos,num = dfs(v, pos)
            if pos>=0:
                return pos,None
            ans = max(ans, num+1)
    done[u] = True
    hist.pop()
    if ans==-float("inf"):
        ans = 0
    return pos,ans
ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos,val = dfs(u, -1)
    if pos>=0:
        print(-1)
        break
    else:
        ans = max(ans, val)
else:
    print(ans+1)

Submission status: Wrong Answer

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

N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
P=[-1]*M
def bfs(u):
  P[u]=0
  B.append(u)
  queue=deque([u])
  while queue:
    v=queue.popleft()    
    for i in D[v]:
      if i in B:
        ans=-1
        break
      if P[v]+1>P[i]:
        P[v]+1>P[i]
        P[i]=P[v]+1
        queue.append(i)
ans=-1
for i in range(M):
  B=[]
  if len(F[i])==0:
    ans=0
    bfs(i)
  if ans==-1:
    print(-1)
    exit()

if min(P)==-1:
  print(-1)
else:
  print(max(P)+1)

Submission status: Wrong Answer

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

N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
P=[-1]*M
def bfs(u):
  P[u]=0
  B.append(u)
  queue=deque([u])
  while queue:
    v=queue.popleft()    
    for i in D[v]:
      if i in B:
        ans=-1
        break
      if P[v]+1>P[i]:
        P[v]+1>P[i]
        P[i]=P[v]+1
        queue.append(i)
ans=-1
for i in range(M):
  B=[]
  if len(F[i])==0:
    ans=0
    bfs(i)
  if ans==-1:
    print(-1)
    exit()
    
print(max(P)+1)

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

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

N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
P=[-1]*M
ans=0
def bfs(u):
  P[u]=0
  B.append(u)
  queue=deque([u])
  while queue:
    v=queue.popleft()    
    for i in D[v]:
      if i in B:
        ans==-1
        break
      if P[v]+1>P[i]:
        P[v]+1>P[i]
        P[i]=P[v]+1
        queue.append(i)
for i in range(M):
  B=[]
  if len(F[i])==0:
    bfs(i)
  if ans==-1:
    print(-1)
    exit()
print(max(P)+1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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