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:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    D = [[0]*N for _ in range(N)]
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[i][j] = cur
            D[j][i] = cur
            cur += 1
    #A = [LI() for _ in range(N)]
    for i in range(N):
        a = LI()
        for j in range(N-2):
            fr = D[i][a[j]-1]
            to = D[i][a[j+1]-1]
            #print(fr,to)
            V[fr].append(to)

    visited = [False] * node
    calculated = [False] * node
    dp = [1] * node
    # https://mhiro216.hatenablog.com/entry/2019/09/08/142414
    def dfs(v):
        if visited[v]:
            if not calculated[v]:
                return -1  # 計算が終わっていない頂点を2度訪れるのはループがあるということ
            return dp[v]
        visited[v] = True
        for u in V[v]:  # 全ての辺をなめる
            res = dfs(u)
            if res == -1: return -1  # ループがあれば-1を返す
            elif res+1>dp[v]:
                dp[v] = res + 1
        calculated[v] = True
        return dp[v]

    ans = 0
    for i in range(node):
        res = dfs(i)
        ans = max(ans,res)
        if res == -1:
            print('-1')  # ループがあれば-1を返す（問題文の指示）
            return
    print(ans)
    return

def examE2():
    N = I()
    V = defaultdict(set)
    for i in range(N):
        A = LI()
        for j in range(N-2):
            a0, a1 = sorted([i,A[j]-1]), sorted([i,A[j+1]-1])
            V[tuple(a0)].add(tuple(a1))
    #print(V)

    # 閉路検出
    def hasCycle(V):
        visited = defaultdict(lambda: False)

        def dfs(s, p=-1):
            res = False

            if not s in V:
                return False

            for v in V[s]:
                if v == p:
                    continue
                if visited[v]:
                    return True
                visited[v] = True
                res |= dfs(v, s)
                visited[v] = False
                if res:
                    break
            return res

        has_cycle = False
        for i in V.keys():
            if dfs(i):
                has_cycle = True
                break
        #print(has_cycle)
        return has_cycle

    if hasCycle(V):
        print(-1)
        return

    def getMaxLength(V):
        visited = defaultdict(lambda: False)
        def dfs(s,p=-1):
            res = 0

            if not s in V:
                return res+1

            for v in V[s]:
                if v==p:
                    continue
                visited[v] = True
                child = dfs(v, s)
                if res<child:
                    res = child

                visited[v] = False

            return res+1

        max_length = 0

        for i in V.keys():
            length = dfs(i)
            if max_length<length:
                max_length = length

        return max_length

    #ans = getMaxLength(V)
    #print(ans)
    return

def examF():
    # 合ってんのこれ?????
    def calc_L(a,b):
        return (a**2 + b**2)**(1/2)
    N = I()
    X = [[]for _ in range(N)]
    for i in range(N):
        x,y = LI()
        d = math.degrees(math.atan2(y,x))
        if d<0:
            d += 360
        X[i] = [d,x,y]
    X.sort()
    #print(X)
    ans = 0
    for i in range(N):
        cur_X = 0; cur_Y = 0
        for d2,x2,y2 in (X[i:] + X[:i]):
            if calc_L(cur_X+x2,cur_Y+y2)<calc_L(cur_X,cur_Y):
                continue
            cur_X += x2
            cur_Y += y2

        now = calc_L(cur_X,cur_Y)
        if now>ans:
            ans = now

    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE2()

"""

"""

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, Counter

    n = int(readline())
    mat = [list(map(int, readline().split())) for _ in range(n)]

    edge = defaultdict(list)
    count = Counter()

    for x in range(1, n + 1):
        for j in range(n - 2):
            y = mat[x - 1][j]
            z = mat[x - 1][j + 1]
            uf, us = min(x, y), max(x, y)
            vf, vs = min(x, z), max(x, z)
            edge[(uf, us)].append((vf, vs))
            count[(uf, us)] += 0
            count[(vf, vs)] += 1

    ans = 0
    while count:
        ans += 1
        today = [key for key, val in count.items() if val == 0]
        if not today:
            print(-1)
            return

        for cur_match in today:
            for nx_match in edge[cur_match]:
                count[nx_match] -= 1
            count[cur_match] = -1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    start = time.time()
    N = int(input())
    A = [tuple(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    min_id = 0
    M = (N*(N-1)) // 2

    while(min_id < N-1):
        now = time.time()
        if now - start > 1.9:
            ans = M+1
            break
        ans += 1
        if ans > M:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    a = A[i][id[i]]
                    if Lock[a-1] == i and i not in tmp:
                        Lock[a-1] = -1
                        id[a-1] += 1
                        tmp.add(a-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > M:
        print(-1)
    else:
        print(ans)


main()

Submission status: Wrong Answer

Solution code:

def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    start = time.time()
    N = int(input())
    A = [tuple(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    min_id = 0
    M = (N*(N-1)) // 2

    while(min_id < N-1):
        now = time.time()
        if now - start > 2:
            ans = M+1
            break
        ans += 1
        if ans > M:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    a = A[i][id[i]]
                    if Lock[a-1] == i and i not in tmp:
                        Lock[a-1] = -1
                        id[a-1] += 1
                        tmp.add(a-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > M:
        print(-1)
    else:
        print(ans)
    print(start)


main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def all_done(arr, N):
    for a in arr:
        if a != N-1:
            return False
    return True

def main():
    N = I()
    G = []
    for i in range(N):
        G.append(LI_())
    t = 0
    next_ix = [0] * N
    fail = False
    _i = 0
    while _i < 10 * N:
        _i += 1
        if fail:
            break
        if all_done(next_ix, N):
            break
        playing = set()
        for i in range(N):
            if t > N * (N-1):
                fail = True
                break

            if i in playing:
                continue
            if next_ix[i] >= N-1:
                continue
            j = G[i][next_ix[i]]
            if next_ix[j] >= N-1:
                fail = True
                break

            if j in playing:
                continue
            if G[j][next_ix[j]] != i:
                continue
            else:
                playing.add(j)
                playing.add(i)
                next_ix[i] += 1
                next_ix[j] += 1
        if len(playing) == 0:
            fail = True
            break
        t += 1
        if t > N * (N-1):
            fail = True
            break
    if fail:
        print("-1")
    else:
        print(t)
main()

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
query = [getList() for i in range(N)]

match = [[-1] * N for i in range(N)]
cnt = 0
for i in range(N):
    for j in range(i + 1, N):
        if i != j:
            match[i][j] = cnt
            match[j][i] = cnt
            cnt += 1

q_alta = []
for i in range(N):
    x1 = query[i][0] - 1
    for j in range(1, N - 1):
        x2 = query[i][j] - 1
        q_alta.append([match[i][x1], match[i][x2]])
        x1 = x2

# 試合数
M = N * (N - 1) // 2

dist = [[] for i in range(M)]
for a, b in q_alta:
    dist[a].append(b)

pos = deque([[0, 0]])
ignore = [-1] * M
ignore[0] = -float('inf')

ans = 0
while len(pos) > 0:
    now, time = pos.popleft()
    time += 1
    ans = max(ans, time)
    for i in dist[now]:
        if ignore[i] != now:
            ignore[i] = now
            pos.append([i, time])
        # ループがあるとNG
        else:
            print(-1)
            exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def all_done(arr, N):
    for a in arr:
        if a != N-1:
            return False
    return True

def main():
    N = I()
    G = []
    for i in range(N):
        G.append(LI_())
    t = 0
    next_ix = [0] * N
    fail = False
    _i = 0
    while _i < 3 * N:
        _i += 1
        if fail:
            break
        if all_done(next_ix, N):
            break
        playing = set()
        for i in range(N):
            if t > N * (N-1):
                fail = True
                break

            if i in playing:
                continue
            if next_ix[i] >= N-1:
                continue
            j = G[i][next_ix[i]]
            if next_ix[j] >= N-1:
                fail = True
                break

            if j in playing:
                continue
            if G[j][next_ix[j]] != i:
                continue
            else:
                playing.add(j)
                playing.add(i)
                next_ix[i] += 1
                next_ix[j] += 1
        if len(playing) == 0:
            fail = True
            break
        t += 1
        if t > N * (N-1):
            fail = True
            break
    if fail:
        print("-1")
    else:
        print(t)
main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def all_done(arr, N):
    for a in arr:
        if a != N-1:
            return False
    return True

def main():
    N = I()
    G = []
    for i in range(N):
        G.append(LI_())
    t = 0
    next_ix = [0] * N
    fail = False

    while True:
        if fail:
            break
        if all_done(next_ix, N):
            break
        playing = set()
        for i in range(N):
            if i in playing:
                continue
            if next_ix[i] >= N-1:
                continue
            j = G[i][next_ix[i]]
            if next_ix[j] >= N-1:
                fail = True
                break

            if j in playing:
                continue
            if G[j][next_ix[j]] != i:
                fail = True
                break
            else:
                playing.add(j)
                playing.add(i)

                next_ix[i] += 1
                next_ix[j] += 1
        t += 1
    if fail:
        print("-1")
    else:
        print(t)
main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque, defaultdict

    n, *aa = [deque(map(int, l.split())) for l in open(0)]

    n = n[0]
    days = 0
    rem = list(range(n))
    while 1:
        today = defaultdict(bool)
        days += 1
    #     print(days, aa)
        complete = True
        new_rem = []
        for i in rem:
            pl = aa[i]
            if not len(aa[i]):
                continue
            else:
                complete = False
                if today[i] and i+1 == aa[pl[0]-1][0]:
                    today[i] = True
                    today[pl[0]-1] = True
        if complete:
            return days-1
        else:
            changed = False
            for i in rem:
                if today[i]:
                    changed = True
                    aa[i].popleft()
                if len(aa[i]):
                    new_rem.append(i)
            if not changed:
                return -1
print(main())

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())

done = [[False]*n for _ in range(n)]
indeg = [[0]*n for _ in range(n)]
adj = [[[] for _ in range(n)] for _ in range(n)]

for i in range(n):
    prev = (-1,-1)
    for j in map(int,input().split()):
        j -= 1
        ni,nj = (i,j) if i < j else (j,i)
        if prev != (-1,-1):
            pi,pj = prev
            adj[pi][pj].append((ni,nj))
            indeg[ni][nj] += 1
        prev = (ni,nj)
            
lst = []
def bfs(si,sj):
    Q = deque()
    Q.append((si,sj))
    done[si][sj] = True
    while Q:
        i,j = Q.popleft()
        lst.append((i+1,j+1))
        for ni,nj in adj[i][j]:
            indeg[ni][nj] -= 1
            if indeg[ni][nj] > 0: continue
            if done[ni][nj]: continue
            Q.append((ni,nj))
            done[ni][nj] = True

for i in range(n):
    for j in range(i+1,n):
        if indeg[i][j] > 0: continue
        if done[i][j]: continue
        bfs(i,j)
# print(lst)

if len(lst) < n*(n-1)//2: ans = -1
else:
    ans = 1
    s = set()
    for i,j in lst:
        if i in s or j in s:
            ans += 1
            s = {i,j}
        else:
            s |= {i,j}
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = []
for i in range(n):
    rs = list(map(int, input().split()))
    rs = [r-1 for r in rs]
    A.append(rs)

cnts = [0] * n
days = 1
while True:
    tekis = []
    # print("Day",days, cnts)
    fin = 0
    for cnt,a in zip(cnts, A):
        if cnt == n-1: 
            tekis.append(-1)
            fin += 1
        else: 
            tekis.append(a[cnt])
    if fin == n: 
        print(days-1)
        exit()
    # 敵の敵が自分だったらマッチング成立
    flg = False
    matched = [False] * n
    for i,teki in enumerate(tekis):
        if matched[teki] or teki==-1:continue
        if tekis[teki] == i:
            cnts[i] += 1
            matched[i] = True
            cnts[teki] += 1
            matched[teki] = True
            flg = True
            # print("{}vs{}".format(i,teki))
    # マッチングが一つも成立しない
    if days > 2000:
        print(-1)
        exit()
    if not flg:
        print(-1)
        exit()
    days += 1

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = []
for i in range(n):
    rs = list(map(int, input().split()))
    rs = [r-1 for r in rs]
    A.append(rs)

cnts = [0] * n
days = 1
while True:
    tekis = []
    # print("Day",days, cnts)
    fin = 0
    for cnt,a in zip(cnts, A):
        if cnt == n-1: 
            tekis.append(-1)
            fin += 1
        else: 
            tekis.append(a[cnt])
    if fin == n: 
        print(days-1)
        exit()
    # 敵の敵が自分だったらマッチング成立
    flg = False
    matched = [False] * n
    for i,teki in enumerate(tekis):
        if matched[teki] or teki==-1:continue
        if tekis[teki] == i:
            cnts[i] += 1
            matched[i] = True
            cnts[teki] += 1
            matched[teki] = True
            flg = True
            # print("{}vs{}".format(i,teki))
    # マッチングが一つも成立しない
    if days > 2000:
        print(-1)
    if not flg:
        print(-1)
        exit()
    days += 1

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = []
for i in range(n):
    rs = list(map(int, input().split()))
    rs = [r-1 for r in rs]
    A.append(rs)

cnts = [0] * n
days = 1
while True:
    tekis = []
    # print("Day",days, cnts)
    fin = 0

    matched = [False]*n
    flg = False
    for i in range(n):
        cnt_me = cnts[i]
        if cnt_me == n-1:
            fin += 1
            continue       
        i_teki = A[i][cnt_me]
        cnt_you = cnts[i_teki]
        if i == A[i_teki][cnt_you]:
            cnts[i] += 1
            cnts[i_teki] += 1
            matched[i] = True
            matched[i_teki] = True
            flg = True

    if fin == n: 
        print(days)
        exit()
    if not flg:
        print(-1)
        exit()
    days += 1

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
n=int(input())
es=[]

for i in range(n):
    *A,=map(int,input().split())
    for j in range(n-2):
        a=A[j]
        x1,y1=min(a-1,i),max(a-1,i)
        b=A[j+1]
        x2,y2=min(b-1,i),max(b-1,i)
        es.append([(x1,y1), (x2,y2)])
#print(es)
v=n*(n-1)//2
outs = defaultdict(list)
ins = defaultdict(int)
for i,j in es:
    outs[i].append(j)
    ins[j] += 1
inkeys=[(i,j) for i in range(n) for j in range(i+1,n)]
#print(outs, ins)
q = deque((v1,0) for v1 in inkeys if ins[v1] == 0)
res = []
while q:
    v1,cnt = q.popleft()
    res.append((v1,cnt))
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append((v2,cnt+1))

if res==[]:
    print(-1)
else:
    print(max([r[1]+1 for r in res]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
n=int(input())
es=[]

for i in range(n):
    *A,=map(int,input().split())
    for j in range(n-2):
        a=A[j]
        x,y=min(a-1,i),max(a-1,i)
        ith=((n-x)+(n-1))*x//2-1+(y-x)
        b=A[j+1]
        x,y=min(b-1,i),max(b-1,i)
        jth=((n-x)+(n-1))*x//2-1+(y-x)
        es.append([ith, jth])
#print(es)
v=n*(n-1)//2
outs = defaultdict(list)
ins = defaultdict(int)
for i,j in es:
    outs[i].append(j)
    ins[j] += 1
#print(outs, ins)
q = deque((v1,0) for v1 in range(n*(n-1)//2) if ins[v1] == 0)
res = []
while q:
    v1,cnt = q.popleft()
    res.append((v1,cnt))
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append((v2,cnt+1))

if res==[]:
    print(-1)
else:
    print(max([r[1]+1 for r in res]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
n=int(input())
es=[]

for i in range(n):
    *A,=map(int,input().split())
    for j in range(n-2):
        a=A[j]
        x,y=min(a-1,i),max(a-1,i)
        ith=((n-x)+(n-1))*x//2-1+(y-x)
        b=A[j+1]
        x,y=min(b-1,i),max(b-1,i)
        jth=((n-x)+(n-1))*x//2-1+(y-x)
        es.append([ith, jth])
#print(es)
v=n*(n-1)//2
outs = defaultdict(list)
ins = defaultdict(int)
for i,j in es:
    outs[i].append(j)
    ins[j] += 1
#print(outs, ins)
q = deque((v1,0) for v1 in range(n*(n-1)//2) if ins[v1] == 0)
res = []
while q:
    v1,cnt = q.popleft()
    res.append((v1,cnt))
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append((v2,cnt+1))

if res==[]:
    print(-1)
else:
    print(res[-1][1]+1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from collections import defaultdict
from itertools import product
INF = float("inf")


def main():
    N = int(input())
    A = [None]*N
    for i in range(N):
        A[i] = list(map(lambda x: int(x)-1, input().split()))

    def f(i, j):
        # 0<i<j<Nを満たすi,jの組を整数へ対応付ける
        if i > j:
            i, j = j, i
        return j-1 + (N-2)*i-i*(i-1)//2

    out = defaultdict(list)
    # 対戦カードをノードとみなし、閉路検出と最長パス探索を行う
    for i in range(N):
        for j in range(N-2):
            out[f(i, A[i][j])].append(f(i, A[i][j+1]))
    # print(out)

    # 閉路検出
    # 始点からのパスを保持しながらDFSする
    hist = [False]*(N*(N-1)//2)

    def dfs(v):
        hist[v] = True
        longpath = 1
        for u in out[v]:
            if hist[u] is False:
                longpath = max(1+dfs(u), longpath)
            else:
                return INF
        hist[v] = False
        return longpath

    longest = dfs(f(0, A[0][0]))
    if longest == INF:
        print(-1)
    else:
        print(longest)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
import heapq
INF = float("inf")


def main():
    # 10**6くらいのループ
    # 毎回、logN以内で閉路を検出できると嬉しい
    # 見るべき場所は、新しく追加したところだけで、即座にわかるのでO(1)か
    N = int(input())
    A = [None]*N
    for i in range(N):
        A[i] = list(map(lambda x: int(x)-1, input().split()))
    # print(A)

    # それぞれの選手の手合進行
    indices = [0]*N
    E = [-1 for _ in range(N)]
    change = []
    for i in range(N):
        # 選手iは次選手A[i][indices[i]]と勝負したい
        E[i] = A[i][indices[i]]
        if E[E[i]] == i:
            # 勝負成立
            change.append(i)
            change.append(E[i])
            indices[i] += 1
            indices[E[i]] += 1
    if len(change) == 0:
        # print("一巡目終了")
        print(-1)
        return

    ans = 0
    while len(change) > 0:
        # print("change", change)
        # print("indices", indices)
        new_change = []
        ans += 1
        for c in change:
            # print("変更", c)
            if indices[c] == N-1:
                continue
            E[c] = A[c][indices[c]]
            if E[E[c]] == c:
                # 勝負成立
                # print("勝負成立, ", c, " vs ", E[c])
                # print(indices)
                new_change.append(c)
                new_change.append(E[c])
                indices[c] += 1
                indices[E[c]] += 1
        change = new_change

    flag = True
    for i in range(N):
        if indices[i] != N-1:
            flag = False
            break
    if flag is False:
        print("満たせずに更新なし")
        # print(indices)
        print(-1)
        return
    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())

I=[[] for i in range(N*~-N//2)]
O=[[] for i in range(N*~-N//2)]

def dfs(g,d):
  if d<N:
    m=-1
    if len(O[g])==0:
      return d+1
    for i in O[g]:
      m=max(m,dfs(i,d+1))
      if m>N:
        break
    return m
  else:
    return N+1

for i in range(N):
  pv=-1
  for j in [int(x)-1 for x in input().split()]:
    v=j*~-j//2+i if i<j else i*~-i//2+j
    if pv!=-1:
      I[v].append(pv)
      O[pv].append(v)
    pv=v

m=-1
for s in range(N*~-N//2):
  if len(I[s])!=0:
    continue
  m=max(m,dfs(s,0))
  if m>N:
    print(-1)
    exit(0)
print(m)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
a_list = []
for i in range(n):
    a_list.append(deque([int(aa) - 1 for aa in input().split()]))
day = 0
battle = 0
for _ in range(n * (n - 1) // 2):
    if battle == n * (n - 1) // 2:
        break
    day += 1
    battle_today = 0
    tomorrow = set([])
    if (day == 1):
        player = set([i for i in range(n)])
    for i in player:
        if len(a_list[i]) == 0:
            continue
        j = a_list[i][0]
        if (i == a_list[j][0]) & (j not in tomorrow) & (len(a_list[j]) > 0):
            tomorrow.add(i)
            tomorrow.add(a_list[i][0])
            battle += 1
            battle_today += 1
            a_list[i].popleft()
            a_list[j].popleft()
    player = tomorrow
    if battle_today == 0:
        day = -1
        break
print(day)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
a_list = []
for i in range(n):
    a_list.append(deque([int(aa) - 1 for aa in input().split()]))
day = 0
battle = 0
for _ in range(n * (n - 1) // 2):
    for j in range(n):
        print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
N = int(input().strip("\n"))
A = [list(map(lambda x :int(x)-1, input().split())) for _ in range(N)]

# 対戦カード (インデックス0>インデックス[1]だけ使う)
all_patterns = [[[] for _ in range(N)] for _ in range(N)]
lines_to_here = [[0 for _ in range(N)] for _ in range(N)]

for i in range(len(A)):
    for j in range(len(A[i])-1):
        playerA = i
        playerB = A[i][j]
        if playerA < playerB:
            playerA, playerB = playerB, playerA
        next_playerA = i
        next_playerB = A[i][j+1]
        if next_playerA < next_playerB:
            next_playerA, next_playerB = next_playerB, next_playerA
        
        all_patterns[playerA][playerB].append([next_playerA,next_playerB])
        lines_to_here[next_playerA][next_playerB] += 1

next_out = deque()
for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] == 0:
            next_out.append([i,j])

if len(next_out) == 0:
    print(-1)
    sys.exit()

print(-1)

Submission status: Wrong Answer

Solution code:
#https://qiita.com/vain0x/items/fbde8b66927b84080811
#http://kmjp.hatenablog.jp/entry/2019/09/01/1000
#2人の選手が互いに相手を次の対戦相手に指定しているとき以外組めない
#したがって貪欲で一意
from collections import deque
import sys

n = int(input())
a = []

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

Q = deque()
for i in range(n):
    Q.append(i)

#nは番兵
Q.append(n)
Done = set()
cnt = 1
rem=n*(n-1)//2
while rem:#Qでは終了判定にならない
    i = Q.popleft()
    if i==n:
        if not Q:
            break
        cnt += 1
        Q.append(n)
        Done=set()
        continue
    if i not in Done and a[i]:
        p = a[i].pop()
        if p not in Done:##この判定しないと1日に複数回試合することになる
            if a[p][-1]==i:
                Q.append(i)
                Q.append(p)
                a[p].pop()
                Done.add(p)###
                Done.add(i)
                rem-=1
        else:#戻す
            a[i].append(p)
       
if rem:
    print(-1)
    sys.exit()
        
print(cnt)