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
from collections import defaultdict, deque
input = lambda: sys.stdin.readline().rstrip()

graph = defaultdict(list)
deg = defaultdict(int)
n = int(input())
m = n * (n-1) // 2

for i in range(n):
    a = list(map(int, input().split()))
    for j in range(n-2):
        v = tuple({i, a[j]-1})
        u = tuple({i, a[j+1]-1})
        graph[v].append(u)
        deg[u] += 1

t = [v for v in graph if deg[v] == 0]
q = deque(t)

while q:
    v = q.popleft()
    for u in graph[v]:
        deg[u] -= 1
        if deg[u] == 0:
            q.append(u)
            t.append(u)

if len(t) != m:
    print(-1)
    exit()

dp = defaultdict(int)
for v in t:
    for u in graph[v]:
        dp[u] = max(dp[u], dp[v] + 1)

print(dp[t[-1]]+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]
S = set()
now = [0]*N
cnt = 0
for i in range(N):
    a = A[i][0]
    if A[a][0] == i and now[a] == 0:
        S.add(i)
        S.add(a)
def add(a):
    global cnt
    if now[a]>=N-1:
        return
    b = A[a][now[a]]
    S.discard(b)
    if a in used or b in used:
        return
    if A[b][now[b]] == a:
        next_S.add(a)
        next_S.add(b)
        used.add(a)
        used.add(b)

ans = 0
while S:
    ans+=1
    next_S = set()
    used = set()
    for a in S:
        now[a]+=1
    while S:
        a = S.pop()
        add(a)
    S = next_S
if all(now[i] == N-1 for i in range(N)):
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]
S = set()
now = [0]*N
cnt = 0
for i in range(N):
    a = A[i][0]
    if A[a][0] == i and now[a] == 0:
        S.add(i)
        S.add(a)
def add(a):
    global cnt
    if now[a]>=N-1:
        return
    b = A[a][now[a]]
    S.discard(b)
    if A[b][now[b]] == a:
        next_S.add(a)
        next_S.add(b)

ans = 0
while S:
    ans+=1
    next_S = set()
    for a in S:
        now[a]+=1
    while S:
        a = S.pop()
        add(a)
    S = next_S
if all(now[i] == N-1 for i in range(N)):
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]
S = set()
now = [0]*N
cnt = 0
for i in range(N):
    a = A[i][0]
    if A[a][0] == i and now[a] == 0:
        S.add(i)
        S.add(a)
        now[i]+=1
        now[a]+=1
        cnt+=1
def add(a):
    global cnt
    if now[a]>=N-1:
        return
    b = A[a][now[a]]
    S.discard(b)
    if now[b]>=N-1:
        return
    if A[b][now[b]] == a:
        cnt+=1
        now[a]+=1
        now[b]+=1
        next_S.add(a)
        next_S.add(b)

ans = 1
while S:
    next_S = set()
    while S:
        a = S.pop()
        add(a)
    S = next_S
    ans+=1
if cnt == N*(N-1)//2:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())

N = next(read)
A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
days = 1
available_players = deque(range(1, N + 1))
next_opponent = [0] * (N + 1)
played = set()

while available_players:
    player = available_players.popleft()
    if not A[player]:
        continue

    opponent = A[player].popleft()
    if next_opponent[opponent] == player:
        available_players.append(player)
        available_players.append(opponent)
        next_opponent[player] = 0
        next_opponent[opponent] = 0
        if player in played:
            days += 1
            played = set()
        else:
            played.add(player)
            played.add(opponent)
    else:
        next_opponent[player] = opponent

days += 1
for i in A:
    if len(i) > 0:
        print(-1)
        exit()
else:
    print(days)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())

N = next(read)
A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
day = 0

while True:
    done = set()
    for i in range(1, N + 1):
        if i not in done and A[i]:
            if A[A[i][0]][0] == i and A[i][0] not in done:
                done.add(A[A[i][0]].popleft())
                done.add(A[i].popleft())

    day += 1
    if len(done) == 0:
        for i in A:
            if len(i) > 0:
                print(-1)
                exit()
        else:
            print(day)
            exit()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())

N = next(read)
A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
day = 0

while True:
    done = set()
    for i in range(1, N + 1):
        if i not in done and A[i]:
            if A[A[i][0]][0] == i:
                done.add(A[A[i][0]].popleft())
                done.add(A[i].popleft())

    day += 1
    if len(done) == 0:
        for i in A:
            if len(i) > 0:
                print(-1)
                exit()
        else:
            print(day)
            exit()

Submission status: Wrong Answer

Solution code:
import functools

n=int(input())
arr=[0]
check = [0]
checkInd = [0]*(n+1)
for j in range(1,n+1):
    arr.append([0]*(n+1))
    check.append([])
    for i,x in enumerate(input().split(), 1):
        arr[j][int(x)] = i
        check[j].append(int(x))


def cmp(x, y):
    a,b=x
    c,d=y
    if len(set((a,b,c,d))) == 4:
        return 0
    t=[a,b,c,d]
    if t.count(b) > 1:
        a,b=b,a
    if t.count(d) > 1:
        c,d=d,c

    if arr[a][d] < arr[a][b]:
        return 1
    return -1

matches=[(a, b) for a in range(1,n+1) for b in range(a+1, n+1)]
matches.sort(key=functools.cmp_to_key(cmp))
days = 1
seen = set()
for a,b in matches:
    if a in seen or b in seen:
        days += 1
        seen = set((a,b))
    else:
        seen.add(a)
        seen.add(b)
    if check[a][checkInd[a]] != b or check[b][checkInd[b]] != a:
        print(-1)
        break
    checkInd[a] += 1
    checkInd[b] += 1
else:
    print(days)

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = [list(map(lambda x: int(x) - 1, input().rstrip('\n').split())) for _ in range(n)]
    ps = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])
    for i in range(10 ** 10):
        fq = collections.defaultdict(int)
        if i > 5:
            exit()
        while ql:
            d, p = ql.popleft()
            if d == i:
                if ps[p] < n - 1:
                    np = a[p][ps[p]]
                    if ps[np] < n - 1:
                        rp = a[np][ps[np]]
                        if p == rp:
                            if p not in fq and np not in fq:
                                fq[p]
                                fq[np]
                                ps[p] += 1
                                if ps[p] < n - 1:
                                    ql.append([d+1, p])
                                ps[np] += 1
                                if ps[np] < n - 1:
                                    ql.append([d+1, np])
            else:
                ql.appendleft([d, p])
                break
        else:
            print(i + 1 if sum(ps) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()

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
while len(Q)>1:
    i = Q.popleft()
    if i==n:
        cnt += 1
        Q.append(n)
    if i<n 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)###
            else:#戻す
                a[i].append(p)
        else:
            Done.remove(p)
        
for i in range(n):
    if len(a[i])>0:
        print(-1)
        sys.exit()
        
print(cnt)

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
while len(Q)>1:
    i = Q.popleft()
    if i==n:
        cnt += 1
        Q.append(n)
    if i<n 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()
            else:
                a[i].append(p)
        else:
            Done.remove(p)
        
for i in range(n):
    if len(a[i])>0:
        print(-1)
        sys.exit()
        
print(cnt)

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)
cnt = 1
while len(Q)>1:
    i = Q.popleft()
    if i==n:
        cnt += 1
        Q.append(n)
    if i<n and a[i]:
        p = a[i].pop()
        if a[p][-1]==i:
            Q.append(i)
            Q.append(p)
            a[p].pop()
        else:
            a[i].append(p)
        
for i in range(n):
    if len(a[i])>0:
        print(-1)
        sys.exit()
        
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
node = [[1]*N for _ in range(N)]
side = [[[]for _ in range(N)]for _ in range(N)] 
for i in range(N):
    A = list(map(int,input().split()))
    for j in range(N-2):
        a,b = min(i,A[j]-1),max(i,A[j]-1)
        c,d = min(i,A[j+1]-1),max(i,A[j+1]-1)
        side[i][j].append([c,d])
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
node = [[1]*N for _ in range(N)]
side = [[[]for _ in range(N)]for _ in range(N)] 
for i in range(N):
    A = list(map(int,input().split()))
    for j in range(N-2):
        a,b = min(i,A[j]-1),max(i,A[j]-1)
        c,d = min(i,A[j+1]-1),max(i,A[j+1]-1)
        side[a][b].append([c,d])
for _ in range(N-1):
    for i in range(N):
        for j in range(N):
            for a,b in side[i][j]:
                node[a][b] = max(node[i][j]+1,node[a][b])

ans = max(max(node[i])for i in range(N))

for i in range(N):
    for j in range(N):
        for a,b in side[i][j]:
             node[a][b] = max(node[i][j]+1,node[a][b])

c = max(max(node[i])for i in range(N))  
if ans == c:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
node = [[1]*N for _ in range(N)]
side = [[[]for _ in range(N)]for _ in range(N)] 
for i in range(N):
    A = list(map(int,input().split()))
    for j in range(N-2):
        a,b = min(i,A[j]-1),max(i,A[j]-1)
        c,d = min(i,A[j+1]-1),max(i,A[j+1]-1)
        side[a][b].append([c,d])
rangeN = range(N)
for _ in range(N-1):
    for i in rangeN:
        for j in rangeN:
            for a,b in side[i][j]:
                node[a][b] = max(node[i][j]+1,node[a][b])

ans = max(max(node[i])for i in range(N))

for i in rangeN:
    for j in rangeN:
        for a,b in side[i][j]:
             node[a][b] = max(node[i][j]+1,node[a][b])

c = max(max(node[i])for i in range(N))  
if ans == c:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
# 2019-11-17 20:44:23(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n = int(sys.stdin.readline().rstrip())
    table = [None] + [collections.deque(int(x) for x in sys.stdin.readline().split()) for _ in range(n)]
    for i in range(1, n+1):
        print(table[i])
    
    for day in range(1, n * (n - 1) // 2 + 2):
        already_played = []
        finished_count = 0
        for i in range(1, n+1):
            if not table[i]:
                finished_count += 1
                continue
            if i in already_played:
                continue
            j = table[i][0]
            if j in already_played:
                continue
            # if not table[j]:
            #     continue
            if table[j][0] == i:
                already_played += [i, j]
                table[j].popleft()
                table[i].popleft()
        if not already_played:
            if finished_count == n:
                print(day - 1)
                sys.exit()
            print(-1)
            sys.exit()
        




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 5):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if ls[ps] < n - 1 and fq[ps]:
                    nw = a[ps][ls[ps]]
                    if ls[nw] < n - 1 and fq[nw]:
                        rw = a[nw][ls[nw]]
                        if ps == rw:
                            ls[ps] += 1
                            ql.append([d+1, ps])
                            ls[nw] += 1
                            ql.append([d+1, nw])
                            fq[nw] = False
                            fq[ps] = False
            else:
                ql.append([d, ps])
                break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 5):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d <= i:
                if ls[ps] < n - 1 and fq[ps]:
                    fq[ps] = False
                    nw = a[ps][ls[ps]]
                    if ls[nw] < n - 1:
                        rw = a[nw][ls[nw]]
                        if ps == rw and fq[nw]:
                            ls[ps] += 1
                            ql.append([d+1, ps])
                            ls[nw] += 1
                            ql.append([d+1, nw])
                            fq[nw] = False
            else:
                ql.append([d, ps])
                break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 5):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if ls[ps] < n - 1 and fq[ps]:
                    fq[ps] = False
                    nw = a[ps][ls[ps]]
                    if ls[nw] < n - 1:
                        rw = a[nw][ls[nw]]
                        if ps == rw and fq[nw]:
                            ls[ps] += 1
                            ql.append([d+1, ps])
                            ls[nw] += 1
                            ql.append([d+1, nw])
                            fq[nw] = False
            else:
                if d > i:
                    ql.appendleft([d, ps])
                break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 5):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if ls[ps] < n - 1:
                    fq[ps] = False
                    nw = a[ps][ls[ps]]
                    if ls[nw] < n - 1:
                        rw = a[nw][ls[nw]]
                        if ps == rw and fq[nw] and fq[ps]:
                            ls[ps] += 1
                            ql.append([d+1, ps])
                            ls[nw] += 1
                            ql.append([d+1, nw])
                            fq[nw] = False
            else:
                if d > i:
                    ql.appendleft([d, ps])
                break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 5):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if ls[ps] < n - 1 and fq[ps]:
                    fq[ps] = False
                    nw = a[ps][ls[ps]]
                    rw = a[nw][ls[nw]]
                    if ps == rw and fq[nw]:
                        ls[ps] += 1
                        ql.append([d+1, ps])
                        ls[nw] += 1
                        ql.append([d+1, nw])
                        fq[nw] = False
            else:
                if d > i:
                    ql.appendleft([d, ps])
                break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if ls[ps] < n - 1 and fq[ps]:
                    nw = a[ps][ls[ps]]
                    rw = a[nw][ls[nw]]
                    fq[ps] = False
                    if ps == rw:
                        ls[ps] += 1
                        ql.append([d+1, ps])
                        ls[nw] += 1
                        ql.append([d+1, nw])
                        fq[nw] = False
            else:
                ql.appendleft([d, ps])
                break
        if len(ql) == 0:
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])
    dt = 0
    while ql:
        d, ps = ql.popleft()
        if d == dt:
            if ls[ps] < n - 1:
                nw = a[ps][ls[ps]]
                rw = a[nw][ls[nw]]
                if ps == rw:
                    ls[ps] += 1
                    ql.append([d+1, ps])
                    ls[nw] += 1
                    ql.append([d+1, nw])
        else:
            ql.appendleft([d, ps])
            dt += 1
    print(dt + 1 if sum(ls) == n * (n - 1) else -1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A = []
for _ in range(N):
    a = list(map(int,input().split()))
    A.append(deque([e-1 for e in a]))
ans = 0
while True:
    ans += 1
    if not any(map(len,A)):
        print(ans)
        exit()
    player = []
    for i in range(N):
        if len(A[i]) == 0:
            continue
        else:
            if i not in player and A[i] not in player:
                player.append(i)
                player.append(A[i])
                A[i].popleft()
    if len(player) == 0:
        print(-1)
        exit()

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
a=[]
m=0
c=0
d=[]
for i in range(n):
    a.append(0)
    d.append(n-1)

while not a==d:
    if c==1:
        break
    b=[]

    for j in range(n):
        if a[j]==(n-1) or a[l[j][a[j]]-1]==(n-1):
            continue
        if j in b or l[j][a[j]]-1 in b:
            continue

        if l[l[j][a[j]]-1][a[l[j][a[j]]-1]]==j+1:
            
            a[l[j][a[j]]-1]+=1
            b.append(j)
            b.append(l[j][a[j]]-1)
            a[j]+=1
        else:
            c=1
            print(-1)
            break
    m+=1          

if not c==1:
    print(m)

Submission status: Wrong Answer

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

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

AA = [[j for j in i] for i in A]

ID = [[-1] * n for i in range(n)]
id_ = 0
for i in range(n):
    for j in range(i+1,n):
        ID[i][j] = id_
        ID[j][i] = id_
        id_ += 1

for i in range(n):
    for j in range(n-1):
        A[i][j] = ID[i][A[i][j]]

M = [[] for i in range(id_)]
IN = [0] * id_
for i in range(n):
    for j in range(n-2):
        M[A[i][j]].append(A[i][j+1])
        IN[A[i][j+1]] +=1
# print(A)
# print(M)

# 以下、トポロジカルソート

S = []
s = 0

for i in range(id_):
    if IN[i] == 0:
        S.append(i)

while s < len(S):
    for x in M[S[s]]:
        IN[x] -= 1
        print(x,IN)
        if IN[x] == 0:
            S.append(x)
    s += 1

# print(S)

if len(S) < id_:
    print(-1)
else:
    T = [1] * id_
    for i in range(id_):
        for j in M[S[i]]:
            T[j] = max(T[j], T[S[i]] + 1)
    print(max(T))


# 以下、閉路検出(今は削除)

# V = [0] * id_
# S = [0]
# V[0] = 1

# import sys

# def visit(x):
#     if V[x] == 1:
#         print(-1)
#         sys.exit()
#     elif V[x] == 0:
#         V[x] = 1
#         for i in M[x]:
#             visit(i)
#         V[x] = 2

# for i in range(id_):
#     if V[i] == 0:
#         visit(i)
# print("heironasi")

# 閉路検出ここまで

Submission status: Wrong Answer

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

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

AA = [[j for j in i] for i in A]

ID = [[-1] * n for i in range(n)]
id_ = 0
for i in range(n):
    for j in range(i+1,n):
        ID[i][j] = id_
        ID[j][i] = id_
        id_ += 1

for i in range(n):
    for j in range(n-1):
        A[i][j] = ID[i][A[i][j]]

M = [[] for i in range(id_)]
for i in range(n):
    for j in range(n-2):
        M[A[i][j]].append(A[i][j+1])

# print(A)

# 以下、閉路検出

V = [0] * id_
S = [0]
V[0] = 1

import sys

def visit(x):
    if V[x] == 1:
        print(-1)
        sys.exit()
    elif V[x] == 0:
        V[x] = 1
        for i in M[x]:
            visit(i)
        V[x] = 2

for i in range(id_):
    if V[i] == 0:
        visit(i)
# print("heironasi")

# 閉路検出ここまで

ans0 = n-1
for ii in range(n):
    i = ii
    ans = n-1
    aite = AA[i][-1]
    t = AA[aite].index(i)
    while t != n-2:
        ans += n-2-t
        i = aite
        aite = AA[i][-1]
        t = AA[aite].index(i)
    ans0 = max(ans0, ans)
print(ans0)

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs(n,e,fordfs):
    #点の数、スタートの点、有向グラフ
    W = [-1]*n
    #各点の状態量、最短距離とか,見たかどうかとか
    W[e] = 0
    que = deque()
    que.append(e)
    len = [0]*n
    cou = int(0)
    while que:
        now = que.popleft()
        nowv = W[now]
        nowlen = len[now]
        for ne in fordfs[now]:
            cou +=1
            if cou >=n*50:
                return -1
#            if nowv == W[ne]:
                #ループが嫌な時
#                return -1
#            if W[ne] == -1:
            W[ne] = (nowv+1) % 2
            len[ne] = max(nowlen+1,len[ne])
            que.append(ne)
    return max(len)
#########################################################
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N = I()
A = [LI() for _ in range(N)]
vlen = N*(N-1)//2
v = [[] for _ in range(vlen)]
match = [[-1]*N for _ in range(N)]
k = int(0)
for i in range(N):
    for j in range(i+1,N):
        match[i][j] = k
        match[j][i] = k
        k +=1

for i in range(N):
#    print(v)
    for j in range(N-2):
        v[match[i][A[i][j]-1]].append(match[i][A[i][j+1]-1])

anscandi =[0]*vlen
for i in range(vlen):
    anscandi[i] = bfs(vlen,i,v)
    if anscandi[i]==-1:
        ans = -1
        break
if ans==0:
    ans = max(anscandi)+1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs(n,e,fordfs):
    #点の数、スタートの点、有向グラフ
    W = [-1]*n
    #各点の状態量、最短距離とか,見たかどうかとか
    W[e] = 0
    que = deque()
    que.append(e)
    len = [0]*n
    cou = int(0)
    while que:
        now = que.popleft()
        nowv = W[now]
        nowlen = len[now]
        for ne in fordfs[now]:
            cou +=1
            if cou >=n**2//2:
                return -1
#            if nowv == W[ne]:
                #ループが嫌な時
#                return -1
#            if W[ne] == -1:
            W[ne] = (nowv+1) % 2
            len[ne] = max(nowlen+1,len[ne])
            que.append(ne)
    return max(len)
#########################################################
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N = I()
A = [LI() for _ in range(N)]
vlen = N*(N-1)//2
v = [[] for _ in range(vlen)]
match = [[-1]*N for _ in range(N)]
k = int(0)
for i in range(N):
    for j in range(i+1,N):
        match[i][j] = k
        match[j][i] = k
        k +=1

for i in range(N):
#    print(v)
    for j in range(N-2):
        v[match[i][A[i][j]-1]].append(match[i][A[i][j+1]-1])

anscandi =[0]*vlen
for i in range(vlen):
    anscandi[i] = bfs(vlen,i,v)
    if anscandi[i]==-1:
        ans = -1
        break
if ans==0:
    ans = max(anscandi)+1

print(ans)