Problem:


Score : 500 points

Problem Statement

N players will participate in a tennis tournament. We will call them Player 1, Player 2, \ldots, Player N.

The tournament is round-robin format, and there will be N(N-1)/2 matches in total.
Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.

Each player plays at most one matches in a day.

Each player i (1 \leq i \leq N) plays one match against Player A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} in this order.

Constraints

3 \leq N \leq 1000

1 \leq A_{i, j} \leq N

A_{i, j} \neq i

A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} are all different.

Input

Input is given from Standard Input in the following format:

N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}

Output

If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1.

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

All the conditions can be satisfied if the matches are scheduled for three days as follows:

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

4
2 3 4
1 3 4
4 1 2
3 1 2

Sample Output 2

4

All the conditions can be satisfied if the matches are scheduled for four days as follows:

Day 1: Player 1 vs Player 2, Player 3 vs Player 4

Day 2: Player 1 vs Player 3

Day 3: Player 1 vs Player 4, Player 2 vs Player 3

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Wrong Answer

Solution code:
from 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:
                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*20:
                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*6:
                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:
#############################################################
class UnionFind():
    def __init__(self, n):
        # 正==子: 根の頂点番号 / 負==根: 連結頂点数
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        #要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        #要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
        # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):
        # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        # すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        # グループの数を返す
        return len(self.roots())

    def all_group_members(self):
        # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
################################################################################
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*4:
                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)]
cou = int(0)
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 l in match:
#    l.remove(-1)
#print(match)
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])
#        print(v[match[i][j]])

#        v[A[i][j]-1].append(A[i][j+1]-1)

#print(v)
#print(ans)
uf = UnionFind(vlen)
for i,l in enumerate(v):
    for j in l:
        if not uf.same(i, j):
            uf.union(i, j)

#print(uf.all_group_members())

#print(bfs(vlen,0,v))

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:
#############################################################
class UnionFind():
    def __init__(self, n):
        # 正==子: 根の頂点番号 / 負==根: 連結頂点数
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        #要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        #要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
        # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):
        # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        # すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        # グループの数を返す
        return len(self.roots())

    def all_group_members(self):
        # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
################################################################################
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*4:
                return -1
#            if nowv == W[ne]:
                #ループが嫌な時
#                return -1
#            if W[ne] == -1:
            W[ne] = (nowv+1) % 2
            len[ne] = nowlen+1
            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)]
cou = int(0)
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 l in match:
#    l.remove(-1)
#print(match)
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])
#        print(v[match[i][j]])

#        v[A[i][j]-1].append(A[i][j+1]-1)

#print(v)
#print(ans)
uf = UnionFind(vlen)
for i,l in enumerate(v):
    for j in l:
        if not uf.same(i, j):
            uf.union(i, j)

#print(uf.all_group_members())

#print(bfs(vlen,0,v))

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:
#############################################################
class UnionFind():
    def __init__(self, n):
        # 正==子: 根の頂点番号 / 負==根: 連結頂点数
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        #要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        #要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
        # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):
        # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        # すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        # グループの数を返す
        return len(self.roots())

    def all_group_members(self):
        # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
################################################################################
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:
                return -1
#            if nowv == W[ne]:
                #ループが嫌な時
#                return -1
#            if W[ne] == -1:
            W[ne] = (nowv+1) % 2
            len[ne] = nowlen+1
            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)]
cou = int(0)
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 l in match:
#    l.remove(-1)
#print(match)
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])
#        print(v[match[i][j]])

#        v[A[i][j]-1].append(A[i][j+1]-1)

#print(v)
#print(ans)
uf = UnionFind(vlen)
for i,l in enumerate(v):
    for j in l:
        if not uf.same(i, j):
            uf.union(i, j)

#print(uf.all_group_members())

#print(bfs(vlen,0,v))

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:
#############################################################
class UnionFind():
    def __init__(self, n):
        # 正==子: 根の頂点番号 / 負==根: 連結頂点数
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        #要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        #要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
        # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):
        # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        # すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        # グループの数を返す
        return len(self.roots())

    def all_group_members(self):
        # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
################################################################################
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:
                return -1
#            if nowv == W[ne]:
                #ループが嫌な時
#                return -1
#            if W[ne] == -1:
            W[ne] = (nowv+1) % 2
            len[ne] = nowlen+1
            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)]
cou = int(0)
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 l in match:
#    l.remove(-1)
#print(match)
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])
#        print(v[match[i][j]])

#        v[A[i][j]-1].append(A[i][j+1]-1)

#print(v)
#print(ans)
uf = UnionFind(vlen)
for i,l in enumerate(v):
    for j in l:
        if not uf.same(i, j):
            uf.union(i, j)

#print(uf.all_group_members())

#print(bfs(vlen,0,v))

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:
N=int(input())
L = [0]*(N+1)
for i in range(1,N+1):
    L[i] = [int(j) for j in input().split( ) ]
day=0
while True:
    flag=0
    for i in range(1,N+1):
        if L[i]==[]:
            continue
        else: 
            if L[L[i][0]][0]==i:
                del L[i][0]
                flag=1
    if  flag == 0:
        for i in range(1,N+1):
            if L[i] != []:
                day=-1
        break
    day+=1
print(day)

Submission status: Wrong Answer

Solution code:
N=int(input())
L = [0]*(N+1)
for i in range(1,N+1):
    L[i] = [int(j) for j in input().split( ) ]
finished=[]
day=0
while True:
    flag = 0
    for i in range(1,N+1):
        if i in finished or L[i]==[]:
            continue
        else: 
            if L[L[i][0]][0]==i:
                finished.append(i)
                finished.append(L[i][0])
                
                flag = 1
    for i in range(len(finished)):
        j = finished[i]
        del L[j][0]
    finished=[]
    if flag == 0:
        for i in range(1,N+1):
            if L[i] != []:
                day=-1
        break
    day+=1

else:
    print(day)

Submission status: Wrong Answer

Solution code:
N=int(input())
L = [0]*(N+1)
for i in range(1,N+1):
    L[i] = [int(j) for j in input().split( ) ]
finished=[]
day=0
while True:
    flag = 0
    for i in range(1,N+1):
        if i in finished or L[i]==[]:
            continue
        else: 
            if L[L[i][0]][0]==i:
                finished.append(i)
                finished.append(L[i][0])
                
                flag = 1
    for i in range(len(finished)):
        j = finished[i]
        del L[j][0]
    finished=[]
    if flag == 0:
        break
    day+=1
if day==0:
    print('-1')
else:
    print(day)

Submission status: Wrong Answer

Solution code:
N=int(input())
L = [0]*(N+1)
for i in range(1,N+1):
    L[i] = [int(j) for j in input().split( ) ]
finished=[]
day=0
while True:
    flag = 0
    for i in range(1,N+1):
        if i in finished or L[i]==[]:
            continue
        else: 
            if L[L[i][0]][0]==i:
                finished.append(i)
                finished.append(L[i][0])
                
                flag = 1
    for i in range(len(finished)):
        j = finished[i]
        del L[j][0]
    finished=[]
    if flag == 0:
        break
    day+=1
print(day)

Submission status: Wrong Answer

Solution code:
import itertools
import collections
#0-indexed
N = int(input())
A = [[int(_) - 1 for _ in input().split()] for _ in range(N)]
p_c = collections.defaultdict(lambda: [])
c_p_cnt = collections.defaultdict(int)
for i in range(N):
    tmp = []
    for j in A[i]:
        i2, j2 = i, j
        if i > j:
            i2, j2 = j, i
        c_p_cnt[(i2, j2)]
        p_c[(i2, j2)]
        tmp += [(i2, j2)]
    for p, c in zip(tmp, tmp[1:]):
        p_c[p] += [c]
        c_p_cnt[c] += 1
#topological sort
Q = collections.deque([i for i, v in c_p_cnt.items() if v == 0])
if not Q:
    print(-1)
    exit()
D = collections.defaultdict(int)
for p in Q:
    c_p_cnt[p] = 1
while Q:
    p = Q.popleft()
    c_p_cnt[p] -= 1
    if c_p_cnt[p] == -1:
        print(-1)
        exit()
    elif c_p_cnt[p] == 0:
        for c in p_c[p]:
            D[c] = max(D[c], D[p] + 1)
        Q += p_c[p]
print(max(D.values()) + 1)

Submission status: Wrong Answer

Solution code:
import itertools
import collections
#0-indexed
N = int(input())
A = [[int(_) - 1 for _ in input().split()] for _ in range(N)]
p_c = collections.defaultdict(lambda: [])
c_p_cnt = collections.defaultdict(int)
for i in range(N):
    tmp = []
    for j in A[i]:
        i2, j2 = i, j
        if i > j:
            i2, j2 = j, i
        c_p_cnt[(i2, j2)]
        p_c[(i2, j2)]
        tmp += [(i2, j2)]
    for p, c in zip(tmp, tmp[1:]):
        p_c[p] += [c]
        c_p_cnt[c] += 1
#topological sort
Q = collections.deque([i for i, v in c_p_cnt.items() if v == 0])
if not Q:
    print(-1)
    exit()
D = collections.defaultdict(lambda: -100)
for i in Q:
    D[i] = 0
while Q:
    p = Q.popleft()
    if c_p_cnt[p] == -1:
        print(-1)
        exit()
    elif c_p_cnt[p] == 0:
        for c in p_c[p]:
            D[c] = max(D[c], D[p] + 1)
            c_p_cnt[c] -= 1
        Q += p_c[p]
        c_p_cnt[p] -= 1
print(max(D.values()) + 1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    match=[[0]*n for _ in range(n)]
    V=0 # V=n(n-1)/2
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        match[i][j]=V
        V+=1

    def toID(i,j):
        if(i>j): i,j=j,i
        return match[i][j]

    E=[[] for _ in range(V)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(1,n-1):
            E[toID(i,A[j-1])].append(toID(i,A[j]))
    # あとは頂点VのグラフをdfsしてLongest pathの長さを求める
    # -1: unchecked, -2: checked and uncalculated
    dp=[-1]*V
    flag=True
    def dfs(v):
        global flag
        dp[v]=-2
        length=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            if(dp[nv]==-1):
                dfs(nv)
            length=max(length,dp[nv]+1)
        dp[v]=length
    # calculate
    dfs(0)
    print(max(dp)+1)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    match=[[0]*n for _ in range(n)]
    V=0 # V=n(n-1)/2
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        match[i][j]=V
        V+=1

    def toID(i,j):
        if(i>j): i,j=j,i
        return match[i][j]

    E=[[] for _ in range(V)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(1,n-1):
            E[toID(i,A[j-1])].append(toID(i,A[j]))
    # あとは頂点VのグラフをdfsしてLongest pathの長さを求める
    # -1: unchecked, -2: checked and uncalculated
    dp=[-1]*V
    flag=True
    def dfs(v):
        global flag
        dp[v]=-2
        length=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                sys.exit()
            if(dp[nv]==-1):
                dfs(nv)
            length=max(length,dp[nv]+1)
        dp[v]=length
    # calculate
    dfs(0)
    print(max(dp)+1)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    match=[[0]*n for _ in range(n)]
    V=0 # V=n(n-1)/2
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        match[i][j]=V
        V+=1

    def toID(i,j):
        if(i>j): i,j=j,i
        return match[i][j]

    E=[[] for _ in range(V)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(1,n-1):
            E[toID(i,A[j-1])].append(toID(i,A[j]))
    # あとは頂点VのグラフをdfsしてLongest pathの長さを求める
    # -1: unchecked, -2: checked and uncalculated
    dp=[-1]*V
    def dfs(v,p):
        dp[v]=-2
        length=0
        for nv in E[v]:
            if(nv==p): continue
            dfs(nv,v)
            if(dp[nv]==-2):
                print(-1)
                exit()
            length=max(length,dp[nv]+1)
        dp[v]=length
    # calculate
    dfs(0,-1)
    print(max(dp)+1)
resolve()

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
A = [None for i in range(N+1)]
A[0] = [0]
for i in range(1,N+1):
	a = list(map(int,input().split()))
	a.reverse()
	A[i] = [N-1]+a
#print(A)
k = 1
c = -1
while(k>0):
	B = copy.deepcopy(A)
	k = 0
	c += 1
	for i in range(1,N+1):
		#print(i,B[i][B[i][0]],id(A)==id(B),B[1][0])
		if B[B[i][B[i][0]]][B[B[i][B[i][0]]][0]] == i:
			A[i][0] -= 1
			k = 1
	#print(B)
if c <1:
	c=-1
print(c)

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
A = [None for i in range(N+1)]
A[0] = [0]
for i in range(1,N+1):
	a = list(map(int,input().split()))
	a.reverse()
	A[i] = [N-1]+a
#print(A)
k = 1
c = -1
while(k>0):
	B = copy.deepcopy(A)
	k = 0
	c += 1
	for i in range(1,N+1):
		#print(i,B[i][B[i][0]],id(A)==id(B),B[1][0])
		if B[B[i][B[i][0]]][B[B[i][B[i][0]]][0]] == i:
			A[i][0] -= 1
			k = 1
	#print(B)
print(c)

Submission status: Wrong Answer

Solution code:
import sys
import collections
N = int(input())

A = []

for i in range(N):
    A.append(collections.deque([int(s) - 1 for s in input().split()]))

nissuu = 0

for i in range(int(10e9)):
    nissuu += 1
    darekayatta = False
    nokoriari = False
    for hito in range(N):
        if len(A[hito]) == 0:
            continue

        nokoriari = True
        teki = A[hito][0]
        tekinoaite = A[teki][0]
        if hito == tekinoaite:
            A[hito].popleft()
            A[teki].popleft()
            darekayatta = True

    if not nokoriari:
        break

    if not darekayatta:
        print(-1)
        sys.exit()

print(nissuu)

Submission status: Wrong Answer

Solution code:
import sys
import collections
N = int(input())

A = []

for i in range(N):
    A.append(collections.deque([int(s) - 1 for s in input().split()]))

nissuu = 0

for i in range(int(10e9)):
    nissuu += 1
    yareru = set(range(0, N))
    darekayatta = False
    nokoriari = False
    for hito in yareru:
        if len(A[hito]) == 0:
            continue

        nokoriari = True
        teki = A[hito].popleft()
        tekinoaite = A[teki].popleft()
        if hito != tekinoaite:
            A[hito].appendleft(teki)
            A[teki].appendleft(tekinoaite)
            continue
        darekayatta = True

    if not nokoriari:
        break

    if not darekayatta:
        print(-1)
        sys.exit()

print(nissuu)

Submission status: Wrong Answer

Solution code:
import collections, itertools
N = int(input())
A = [[int(_) - 1 for _ in input().split()] for _ in range(N)]
B = [0] * N
G = collections.defaultdict(set)
P = collections.defaultdict(int)
for i in range(N):
    for j in range(N - 2):
        x1, y1 = sorted([i, A[i][j]])
        x2, y2 = sorted([i, A[i][j + 1]])
        G[(x1, y1)].add((x2, y2))
        P[(x2, y2)] += 1
        P[(x1, y1)]
        G[(x2, y2)]
Q = collections.deque([])
dist = collections.defaultdict(int)
ans = 1
for pair in P:
    if P[pair] == 0:
        Q += [pair]
        dist[pair] = 1
if not Q:
    print(-1)
    exit()
while Q:
    now = Q.popleft()
    for ne in G[now]:
        if P[ne] == 0:
            print(-1)
            exit()
        P[ne] -= 1
        if P[ne] == 0:
            ans = dist[ne] = dist[now] + 1
            Q += [ne]
print(ans)

Submission status: Wrong Answer

Solution code:
import collections, itertools
N = int(input())
A = [[int(_) - 1 for _ in input().split()] for _ in range(N)]
B = [0] * N
G = collections.defaultdict(set)
P = collections.defaultdict(set)
for i in range(N):
    for j in range(N - 2):
        x1, y1 = sorted([i, A[i][j]])
        x2, y2 = sorted([i, A[i][j + 1]])
        G[(x1, y1)].add((x2, y2))
        P[(x2, y2)].add((x1, y1))
        P[(x1, y1)]
        G[(x2, y2)]
Q = collections.deque([])
dist = collections.defaultdict(int)
ans = 1
for pair in P:
    if len(P[pair]) == 0:
        Q += [pair]
        dist[pair] = 1
if not Q:
    print(-1)
    exit()
while Q:
    now = Q.popleft()
    for ne in G[now]:
        if not now in P[ne]:
            print(-1)
            exit()
        P[ne].remove(now)
        if len(P[ne]) == 0:
            dist[ne] = max(dist[ne], dist[now] + 1)
            ans = max(ans, dist[ne])
            Q += [ne]
print(ans)