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: Accepted

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()
    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)
    #print(V)


    # 閉路検出
    def hasCycle(n,V):
        visited = [False]*n
        used = [False]*n

        def dfs(s, p=-1):
            if used[s]:
                return False

            now_use.add(s)

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

        has_cycle = False

        for i in range(node):
            now_use = set()
            if used[i]:
                continue
            visited[i] = True
            if dfs(i):
                has_cycle = True
                break
            for u in now_use:
                used[u] = True
            visited[i] = False

        return has_cycle

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

    def getMaxLength(n,V):
        visited = [False]*n
        max_lens = [0] * n

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

            for v in V[s]:
                if max_lens[v]>0:
                    child = max_lens[v]
                else:
                    visited[v] = True
                    child = dfs(v, s)
                    visited[v] = False
                if res<child:
                    res = child
            max_lens[s] = res + 1

            return res+1

        for i in range(n):
            if max_lens[i]>0:
                continue
            length = dfs(i)

        return max(max_lens)

    ans = getMaxLength(node,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: Accepted

Solution code:
from collections import deque
#わからない、テストケース
n=int(input())
#それぞれ長さはn-1
a=[[j-1+n*i if j-1<i else i+n*(j-1) for j in list(map(int,input().split()))] for i in range(n)]
#試合の候補をいれる
d=dict()
for i in range(n):
    if a[i][0] in d:
        d[a[i][0]]+=1
    else:
        d[a[i][0]]=1
#どこまで見たか
b=[0]*n
#最大n(n-1)/2回
ans=0
nextd=deque()
cleard=deque()
changeable1=deque(set([a[i][0] for i in range(n)]))
while len(d):
    ans+=1
    #一個も同じのなかったらむり
    g=True
    changeable2=deque()
    for i in changeable1:
        if d[i]==2:
            g=False
            e,f=i//n,i%n
            cleard.append(i)
            b[e]+=1
            b[f]+=1
            if b[e]<n-1:
                nextd.append(a[e][b[e]])
                changeable2.append(a[e][b[e]])
            if b[f]<n-1:
                nextd.append(a[f][b[f]])
                changeable2.append(a[f][b[f]])
    if g:
        exit(print(-1))
    ln,lc=len(nextd),len(cleard)  
    for _ in range(ln):
        i=nextd.popleft()
        if i in d:
            d[i]+=1
        else:
            d[i]=1
    for _ in range(lc):
        i=cleard.popleft()
        #print(i)
        #print(d)
        d.pop(i)
    changeable1=set(changeable2)
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N = int(readline())
A = [None] * N
for i in range(N):
  # 後ろからpopできるように逆順リストで持つ
  A[i] = list(map(lambda x:x - 1,map(int,readline().split())))[::-1]
  
# 今日試合ができる可能性がある人リスト
candi = set(range(N))

day = 0
while candi:
  day += 1
  nex = set()
  done = set()
  for player in candi:
    if player in done:
      continue
    # player が試合できるかチェック
    if len(A[player]) == 0:
      continue
    rival = A[player][-1]
    if rival in done:
      continue
    if A[rival][-1] == player:
      # 試合できる
      A[player].pop()
      A[rival].pop()
      if A[player]:
        nex.add(player)
      done.add(player)
      if A[rival]:
        nex.add(rival)
      done.add(rival)
  if len(done) == 0:
    # 一試合もできなかった
    print(-1)
    exit(0)
  candi = nex
  
print(day)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


sys.setrecursionlimit(10**6)


def pair2index(i, j, N):
    return N * i + j


def main():
    N = int(input())
    adj = defaultdict(list)
    for i in range(N):
        A = list(map(lambda x: int(x) - 1, input().split(' ')))
        for j in range(1, N - 1):
            a = A[j - 1]
            from_index = pair2index(min(i, a), max(i, a), N)
            a = A[j]
            to_index = pair2index(min(i, a), max(i, a), N)
            adj[from_index].append(to_index)

    temp_visited = [0 for _ in range(N**2)]
    max_depth = [0 for _ in range(N**2)]

    def dfs(n):
        if temp_visited[n] == 1:
            # 閉路あり
            max_depth[n] = -1
            return -1
        elif max_depth[n] != 0:
            return max_depth[n]
        else:   # max_depth[n] == 0 (未探索)
            temp_visited[n] = 1
            max_d = 0
            for next_n in adj[n]:
                d = dfs(next_n)
                if d == -1:
                    return d
                max_d = max(max_d, d)
            temp_visited[n] = 0
            max_depth[n] = max_d + 1
            return max_d + 1

    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            node = pair2index(i, j, N)
            depth = dfs(node)
            if depth == -1:
                print(-1)
                return
            ans = max(ans, depth)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
a = []
for i in range(n):
    tmp = deque()
    for j in input().split():
        j = int(j)-1
        tmp.append((min(i, j), max(i, j)))
    a.append(tmp)
nxt = []
q = set()
flg = True
for i in range(n):
    t = a[i].popleft()
    if t in q:
        nxt.append(a[t[0]].popleft())
        nxt.append(a[t[1]].popleft())
        q.remove(t)
        flg = False
    else:
        q.add(t)
if flg:
    print(-1)
    exit(0)
ans = 1
while nxt:
    now = nxt[:]
    nxt = []
    flg = True
    for t in now:
        if t in q:
            if a[t[0]]:
                nxt.append(a[t[0]].popleft())
            if a[t[1]]:
                nxt.append(a[t[1]].popleft())
            q.remove(t)
            flg = False
        else:
            q.add(t)
    if flg:
        print(-1)
        exit(0)
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    A = []
    for _ in range(N):
        _a = list(map(lambda x: int(x)-1, input().split()))
        A.append(_a)
    ptrs = [0 for _ in range(N)]
    day = 0
    players = set([i for i in range(N)])
    finished = set()
    yest_players = set([i for i in range(N)])
    while True:
        todays_players = set()
        matched = False
        if len(finished) == N:
            break
        #print("------")
        for home in yest_players:
            if home in finished:
                continue
            away = A[home][ptrs[home]]
            if away in finished:
                continue
            #print(home, away)
            away_opp = A[away][ptrs[away]]
            if home in todays_players or away in todays_players:
                continue
            if home == away_opp:
                ptrs[home] += 1
                ptrs[away] += 1
                todays_players.add(home)
                todays_players.add(away)
                matched = True
                if ptrs[home] == N-1:
                    finished.add(home)
                if ptrs[away] == N-1:
                    finished.add(away)
        yest_players = todays_players
        #print(ptrs)
        if matched:
            day += 1
        else:
            day = -1
            break
    print(day)





if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
import sys

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


def main():
    def calc_id(x, y):
        return min(x, y) * 10007 + max(x, y)

    from collections import defaultdict, Counter, deque
    from copy import copy

    n = int(readline())

    edge = defaultdict(list)
    count = Counter()

    for x in range(1, n + 1):
        a = list(map(int, readline().split()))
        count[calc_id(x, a[0])] += 0
        for j in range(n - 2):
            y = a[j]
            z = a[j + 1]
            u_id = calc_id(x, y)
            v_id = calc_id(x, z)
            edge[u_id].append(v_id)
            count[v_id] += 1

    ans = 0
    rem = n * (n - 1) // 2
    que = deque()
    for key, val in count.items():
        if val == 0:
            que.append(key)
    que_tomorrow = deque()

    while rem:
        ans += 1
        if not que:
            print(-1)
            return
        while que:
            cur_match = que.popleft()
            for nx_match in edge[cur_match]:
                count[nx_match] -= 1
                if count[nx_match] == 0:
                    que_tomorrow.append(nx_match)
            rem -= 1
        que = copy(que_tomorrow)
        que_tomorrow.clear()

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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
            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: Accepted

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

def main():
    n = int(input())
    al = []
    al.append(deque([]))
    for _ in range(n):
        row = list(map(int, input().split()))
        al.append(deque(row))

    # print(al)

    day = 0
    cnt = 0
    max_cnt = n*(n-1)//2
    check_il = [i for i in range(1,n+1)]
    while True:
        next_check_il = check_il[:]
        check_il = []
        day += 1
        already_fights = set()
        update_flag = False
        for i in next_check_il:
            al_i = al[i]
            if not al_i or i in already_fights: continue
            i_next_rival = al_i[0]

            al_rival_i = al[i_next_rival]
            if not al_rival_i or i_next_rival in already_fights: continue
            i_next_rival_rival = al_rival_i[0]

            if i_next_rival_rival == i:
                al[i].popleft()
                al[i_next_rival].popleft()
                already_fights.add(i)
                already_fights.add(i_next_rival)
                check_il.append(i)
                check_il.append(i_next_rival)
                cnt += 1
                update_flag = True
            else:
                continue

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

        if cnt == max_cnt:
            break

    print(day)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

graph = [[] for _ in range(N * N)]
ins = [0] * (N * N)

for i, nodes in enumerate(X):
    for j1, j2 in zip(nodes[:-1], nodes[1:]):
        n1 = max(i, j1 - 1) * N + min(i, j1 - 1)
        n2 = max(i, j2 - 1) * N + min(i, j2 - 1)
        graph[n1].append(n2)
        ins[n2] += 1

dist = [0] * (N * N)
visited = [False] * (N * N)
q = deque()
for i in range(N):
    visited[N * i + i] = True

for i, v in enumerate(ins):
    if v == 0:
        q.append(i)
        visited[i] = True
        dist[i] = 1

while q:
    u = q.popleft()
    for v in graph[u]:
        if visited[v]:
            continue

        ins[v] -= 1
        if ins[v] == 0:
            visited[v] = True
            dist[v] = dist[u] + 1
            q.append(v)
            
print(max(dist) if all(visited) else -1)

Submission status: Accepted

Solution code:
from collections import deque

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

graph = [[] for _ in range(N * N)]
ins = [0] * (N * N)

for i, nodes in enumerate(X):
    for j1, j2 in zip(nodes[:-1], nodes[1:]):
        n1 = max(i, j1 - 1) * N + min(i, j1 - 1)
        n2 = max(i, j2 - 1) * N + min(i, j2 - 1)
        graph[n1].append(n2)
        ins[n2] += 1

dist = [0] * (N * N)
visited = [False] * (N * N)
q = deque()
for i in range(N):
    visited[N * i + i] = True

for i, v in enumerate(ins):
    if v == 0:
        q.append((i, 1))

while q:
    u, d = q.popleft()
    visited[u] = True
    dist[u] = d

    for v in graph[u]:
        if visited[v]:
            continue
            
        ins[v] -= 1
        if ins[v] == 0:
            q.append((v, d + 1))
            
print(max(dist) if all(visited) else -1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
n = int(input())
maxv = n*(n-1)//2
to = [[] for _ in range(maxv)]
vid = [[-1]*n for _ in range(n)]
def toId(i,j):
    if i > j: i,j = j,i
    return vid[i][j]
    
visited = [False]*maxv
calculated = [False]*maxv
dp = [0]*maxv
def dfs(v):
    if visited[v]:
        if not calculated[v]: return -1
        return dp[v]
    visited[v] = True
    dp[v] = 1
    for u in to[v]:
        res = dfs(u)
        if res == -1: return -1
        dp[v] = max(dp[v], res+1)
    calculated[v] = True
    return dp[v]

a = [[int(i)-1 for i in input().split()] for _ in range(n)]
v = 0
for i in range(n):
    for j in range(i+1,n):
        vid[i][j] = v
        v += 1
for i in range(n):
    for j in range(n-1): a[i][j] = toId(i,a[i][j])
    for j in range(n-2): to[a[i][j+1]].append(a[i][j])
ans = 0
for i in range(maxv):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, res)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = []
    for _ in range(n):
        t = deque(list((map(lambda x: int(x) - 1, input().split()))))
        A.append(t)

    que = deque(list(range(n)))
    res = 0
    emp = [False] * n
    while que:
        next_que = deque([])
        check = set()
        while que:
            i = que.popleft()
            if A[i]:
                idx = A[i][0]
                if i not in check and idx not in check and A[idx][0] == i:
                    A[i].popleft()
                    A[idx].popleft()
                    next_que.append(i)
                    next_que.append(idx)
                    check.add(i)
                    check.add(idx)
            else:
                emp[i] = True
        que = next_que
        if que:
            res += 1
    else:
        print(res if all(emp) else -1)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    A = [0] * N
    for i in range(N):
        A[i] = [int(s) - 1 for s in reversed(readline().split())]

    S = set()

    def check(i):
        if not A[i]:
            return
        j = A[i][-1]
        if i == A[j][-1]:
            if i > j:
                i, j = j, i
            S.add((i, j))

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

    day = 0
    matches = 0
    while S:
        day += 1
        S, S_prev = set(), S
        for i, j in S_prev:
            A[i].pop()
            A[j].pop()
            matches += 1
        for i, j in S_prev:
            check(i)
            check(j)

    if matches == N * (N - 1) // 2:
        ans = day
    else:
        ans = -1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    A = [0] * N
    for i in range(N):
        A[i] = [int(s) - 1 for s in readline().split()]

    M = N * (N - 1) // 2

    total_mathces = 0
    changed = set(range(N))
    for day in range(M):
        matches = 0
        changed_prev, changed = changed, set()
        for i in changed_prev:
            if i in changed or not A[i]:
                continue
            j = A[i][-1]
            if j not in changed and i == A[j][-1]:
                changed.add(i)
                changed.add(j)
                A[i].pop()
                A[j].pop()
                matches += 1

        if matches == 0:
            ans = -1
            break

        total_mathces += matches
        if total_mathces == M:
            ans = day + 1
            break

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections
from collections import defaultdict

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [[int(x) for x in input().split()] for _ in range(N)]

    q = [collections.deque() for j in range(N)]

    for i, a in enumerate(A):
        for aa in a:
            q[i].append(aa)

    ans = 0

    current = defaultdict(int)
    for i, v in enumerate(q):
        current[i + 1] = v[0]

    while True:
        v = set()
        for k in current.keys():
            if k == q[current[k] - 1][0]:
                v.add(k)
                v.add(current[k])

        current = defaultdict(int)

        if len(v) == 0:
            break

        for vv in v:
            q[vv - 1].popleft()
            if len(q[vv - 1]):
                current[vv] = q[vv - 1][0]

        ans += 1

    # 全て空なら
    size = 0
    for i in range(N):
        size += len(q[i])

    if size == 0:
        print(ans)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())

battle=[]

def mainasu(x):
    return int(x)-1

front=[]

for _ in range(n):
    tmp=list(map(mainasu,input().split()))[::-1]
    front.append(tmp.pop())
    battle.append(tmp)

def pri():
    global front,battle,day,checkday
    print(day,front,battle,checkday)

day=0

checkday=[-1]*n

#pri()
cnt=0
while 1:
    flag=0
    for i in range(n):
        if i<n and front[i]<n and i==front[front[i]] and checkday[i]<day and checkday[front[i]]<day:
            flag=1
            if len(battle[front[i]])>0:
                front[front[i]]=battle[front[i]].pop()
                checkday[front[i]]=day
            else:
                front[front[i]]=n
                cnt+=1
            
            if len(battle[i])>0:
                front[i]=battle[i].pop()
                checkday[i]=day
            else:
                front[i]=n
                cnt+=1
    #pri()
    if flag==0:
        break
    
    day+=1


if cnt==n:
    print(day)
else:
    print(-1)

Submission status: Accepted

Solution code:
# E - League
import sys
from collections import deque
from typing import Deque, List

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N = int(readline())
    A: List[Deque[int]] = [deque()] + [
        deque(map(int, line.split())) for line in readlines()
    ]
    matched_games_cnt = 0
    next_opponent, last_games_day = [0] * (N + 1), [0] * (N + 1)
    queue = deque(range(1, N + 1))
    while queue:
        player = queue.popleft()
        if not A[player]:  # The player has finished all games.
            continue
        opponent = A[player].popleft()

        # The opponent will have another game before playing against x.
        if next_opponent[opponent] != player:
            next_opponent[player] = opponent
            continue

        # The opponent's next game is against the player and vice versa.
        matched_games_cnt += 1
        last_games_day[player] = last_games_day[opponent] = (
            max(last_games_day[player], last_games_day[opponent]) + 1
        )
        # No next game is currently planned.
        next_opponent[player] = next_opponent[opponent] = 0
        queue.append(player), queue.append(opponent)

    print(max(last_games_day) if matched_games_cnt == N * (N - 1) // 2 else -1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# E - League
import sys
from collections import deque
from typing import Deque, List

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N = int(readline())
    A: List[Deque[int]] = [deque()] + [
        deque(map(int, line.split())) for line in readlines()
    ]
    matched_games_cnt = 0
    next_games_opponent, last_games_day = [0] * (N + 1), [0] * (N + 1)
    queue = deque(list(range(1, N + 1)))
    while queue:
        player = queue.popleft()
        if not A[player]:  # The player has finished all games.
            continue
        opponent = A[player].popleft()

        # The opponent will have another game before playing against x.
        if next_games_opponent[opponent] != player:
            next_games_opponent[player] = opponent
            continue

        # The opponent's next game is against the player and vice versa.
        matched_games_cnt += 1
        last_games_day[player] = last_games_day[opponent] = (
            max(last_games_day[player], last_games_day[opponent]) + 1
        )
        # No next game is currently planned.
        next_games_opponent[player] = next_games_opponent[opponent] = 0
        queue.append(player), queue.append(opponent)

    print(max(last_games_day) if matched_games_cnt == N * (N - 1) // 2 else -1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
e = [[] for _ in range(n * n)]
co = [0] * (n * n)
for i in range(n):
    a = [int(i)-1 for i in input().split()]
    for j in range(n - 2):
        aa, bb = min(i, a[j]), max(i, a[j])
        cc, dd = min(i, a[j+1]), max(i, a[j+1])
        e[aa * n + bb].append(cc * n + dd)
        co[cc * n + dd] += 1

x = []
for i in range(n * n):
    if co[i] == 0:
        x.append(i)

ans = 0
while x:
    y = []
    for i in x:
        for j in e[i]:
            co[j] -= 1
            if co[j] == 0:
                y.append(j)
    x = y
    ans += 1
if max(co) > 0:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


def dfs(node_id, edges, dp):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges, dp)
        if t == 0:  # looped
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


def main():
    N = int(input())
    A = [[int(e) - 1 for e in input().split()] for _ in range(N)]

    node_id_db = [[0] * N for _ in range(N)]
    v = 0
    for i in range(N):
        for j in range(i + 1, N):
            node_id_db[i][j] = v
            v += 1

    start_nodes = []
    edges = [[] for _ in range(N * (N - 1) // 2)]
    for i in range(N):
        Ai = A[i]
        from_id = get_node_id(i, Ai[0], node_id_db)
        if i < Ai[0]:
            start_nodes.append(from_id)
        for j in range(1, N - 1):
            to_id = get_node_id(i, Ai[j], node_id_db)
            edges[from_id].append(to_id)
            from_id = to_id

    dp = [-1] * (N * (N - 1) // 2)
    print(max(dfs(n, edges, dp) for n in start_nodes))


setrecursionlimit(10 ** 6)
main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n = int(input())
A = []
M = [[-1 for _ in range(n)] for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        M[i][j] = cnt
        M[j][i] = cnt
        cnt += 1
ans = 0
nodes = []
adjacent_list = [[] for i in range(n*(n-1)//2)]
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in tmp[1:]:
        adjacent_list[M[i][pre]].append(M[i][j-1])
        pre = j - 1
#まず、閉路検
seen = defaultdict(lambda: False)
visited = defaultdict(lambda: False)
def check(node):
    if visited[node]:
        return
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if not adjacent_list[node]:
        return 1
    if finish[node]:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = tmp
    return finish[node]
finished = set()
finish = [0 for i in range(n*(n-1)//2)]
for i in range(n*(n-1)//2):
    check(i)
    dfs_path(i)
print(max(max(finish), 1))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
n=int(input())
v=n*(n-1)//2
es=[[] for _ in range(v)]

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[ith].append(jth)

outs = defaultdict(list)
ins = defaultdict(int)

for v1 in range(v):
    for v2 in es[v1]:
        outs[v1].append(v2)
        ins[v2] += 1

q = deque((v1,0) for v1 in range(v) 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))
x=len(res)
if x!=v:
    print(-1)
else:
    print(res[-1][1]+1)