Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

N, K, *DC = map(int, open(0).read().split())

D = tuple(zip(*[iter(DC[:K * K])] * K))
C = tuple(zip(*[iter(DC[K * K:])] * N))

A = [Counter() for _ in range(3)]
for k in range(K):
    for i in range(N):
        for j in range(N):
            A[(i + j) % 3][k] += D[C[i][j] - 1][k]

ans = float("inf")
for i in range(K):
    for j in range(K):
        for k in range(K):
            if i == j or j == k or k == i:
                continue
            ans = min(ans, A[0][i] + A[1][j] + A[2][k])

print(ans)

Fixed submission:

from collections import Counter

N, K, *DC = map(int, open(0).read().split())

D = tuple(zip(*[iter(DC[:K * K])] * K))
C = tuple(zip(*[iter(DC[K * K:])] * N))

A = [Counter() for _ in range(3)]
for k in range(K):
    for i in range(N):
        for j in range(N):
            A[(i + j) % 3][k] += D[C[i][j] - 1][k]

ans = float("inf")
for i in range(K):
    for j in range(K):
        for k in range(K):
            if i == j or j == k or k == i:
                continue
            ans = min(ans, A[0][i] + A[1][j] + A[2][k])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math

def combinations_count(n, r):
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r)) % 998244353)



N, R, B, K = [int(i) for i in input().split()]
G = R + B

lst = []
for i in range(N + 1):
    if R * i > K:
        break
    for j in range(N + 1 - i):
        if R * i + G * j > K:
            break
        k = (K - R * i - G * j) // B
        if R * i + G * j + B * k == K:
            lst.append((i, j, k))

result = 0
for l in lst:
    result += combinations_count(N, l[0]) * combinations_count(N - l[0], l[1]) * combinations_count(N - l[0] - l[1], l[2])

print(result)

Fixed submission:
mod = 998244353

class ModComb:
    def __init__(self, MAX):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

N, A, B, K = map(int, input().split())

mc = ModComb(3 * 10 ** 5 + 10)

ans = 0
for a in range(N + 1):
    b, r = divmod(K - A * a, B)
    if r != 0:
        continue
    ans += mc.nCk(N, a) * mc.nCk(N, b) % mod
    ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
K = int(input())

N = len(S)

memo = set()
for i in range(N):
    for j in range(i, N):
        memo.add(S[i:j + 1])

print(sorted(memo)[K - 1])

Fixed submission:
S = input()
K = int(input())

N = len(S)

memo = []
for i in range(N):
    for d in range(1, min(K, N - i) + 1):
        memo.append(S[i:i + d])

print(sorted(set(memo))[K - 1])

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
K = int(input())

memo = set()

result = []
lst = []
for si in s:
    temp = []
    for li in lst:
        ss = li + si
        if ss not in memo:
            temp.append(li + si)
            memo.add(ss)
    temp.append(si)
    result.extend(temp)
    lst = temp

temp = list(set(result))
temp.sort()
print(temp[K - 1])


Fixed submission:
S = input()
K = int(input())

N = len(S)

memo = []
for i in range(N):
    for d in range(1, min(K, N - i) + 1):
        memo.append(S[i:i + d])

print(sorted(set(memo))[K - 1])

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
K = int(input())

result = []
lst = []
for si in s:
    temp = []
    for li in lst:
        temp.append(li + si)
    temp.append(si)
    result.extend(temp)
    lst = temp

temp = list(set(result))
temp.sort()
print(temp[K - 1])


Fixed submission:
S = input()
K = int(input())

N = len(S)

memo = []
for i in range(N):
    for d in range(1, min(K, N - i) + 1):
        memo.append(S[i:i + d])

print(sorted(set(memo))[K - 1])
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
K = int(input())

S = list(set(s for s in (S[i:j] for i in range(len(S)) for j in range(i + 1, len(S) + 1)) if len(s) <= K))
S.sort()
print(S[K - 1])


Fixed submission:
S = input()
K = int(input())
N = len(S)

C = list(set(S[i:i + j + 1] for i in range(N) for j in range(K) if i + j < N))
C.sort()
print(C[K - 1])

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
K = int(input())

S = list(set(S[i:j] for i in range(len(S)) for j in range(i + 1, len(S) + 1)))
S.sort()
print(S[K - 1])


Fixed submission:
S = input()
K = int(input())
N = len(S)

C = list(set(S[i:i + j + 1] for i in range(N) for j in range(K) if i + j < N))
C.sort()
print(C[K - 1])
Buggy python submission (verdict: Runtime Error):
def solve():
    for i in range(1, W):
        for j in range(1, H):
            if s[i][j] == "#":
                if s[i + 1][j] == "." and s[i][j + 1] == "." and s[i-1][j] == "." and s[i][j-1] == ".":
                    print("No")
                    return;
    else:
        print("Yes")


H, W = [int(i) for i in input().split()]
s = [["."] * (W + 2)]
for _ in range(H):
    sh = ["."] + list(input()) + ["."]
    s.append(sh)
s.append([["."] * (W + 2)])
solve()





Fixed submission:
def solve():
    for i in range(1, H):
        for j in range(1, W):
            if s[i][j] == "#":
                if s[i + 1][j] == "." and s[i][j + 1] == "." and s[i-1][j] == "." and s[i][j-1] == ".":
                    print("No")
                    return;
    else:
        print("Yes")


H, W = [int(i) for i in input().split()]
s = [["."] * (W + 2)]
for _ in range(H):
    sh = ["."] + list(input()) + ["."]
    s.append(sh)
s.append([["."] * (W + 2)])
solve()
Buggy python submission (verdict: Runtime Error):
import bisect

n = int(input())
a = [int(i) for i in input().split()]
a.sort()
max_a = a[n-1]
a.remove(max_a)
result = bisect.bisect_left(a, max_a // 2)
print(max_a, a[result])



Fixed submission:
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
max_a = a[-1]
print(max_a, min(a, key=lambda x: abs(max_a - 2*x)))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
max_a = a[n-1]
a.remove(max_a)
for i in range(max_a // 2, -1, -1):
    if i in a:
        print(max_a, i)
        break
    if max_a - i in a:
        print(max_a, max_a - i)
        break


Fixed submission:
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
max_a = a[-1]
print(max_a, min(a, key=lambda x: abs(max_a - 2*x)))
Buggy python submission (verdict: Time Limit Exceeded):
A, B, K = [int(i) for i in input().split()]
for i in range(A, B+1):
    if i < A + K or B - K < i:
        print(i)


Fixed submission:
A, B, K = map(int, input().split())
if B - A < 2 * K:
    print(*range(A, B + 1), sep="\n")
else:
    print(*range(A, A + K), sep="\n")
    print(*range(B - K + 1,  B + 1), sep="\n")

Buggy python submission (verdict: Runtime Error):
A, B, K = [int(i) for i in input().split()]
ra = list(range(A, B+1))
for i in ra:
    if i < A + K or B - K < i:
        print(i)



Fixed submission:
A, B, K = map(int, input().split())
if B - A < 2 * K:
    print(*range(A, B + 1), sep="\n")
else:
    print(*range(A, A + K), sep="\n")
    print(*range(B - K + 1,  B + 1), sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = [int(i) for i in input().split()]
B = [(-1, -1) for _ in range(H * W)]
for h in range(H):
    A = [int(i) - 1 for i in input().split()]
    for w in range(W):
        B[A[w]] = (h, w)

Q = int(input())
for l, r in [[int(i) - 1 for i in input().split()] for _ in range(Q)]:
    su = 0
    C = B[l:r + 1:D]
    h, w = C[0]
    for nh, nw in C[1:]:
        su += abs(nh - h) + abs(nw - w)
        h, w = nh, nw
    print(su)


Fixed submission:
H, W, D = [int(i) for i in input().split()]
B = [(-1, -1) for _ in range(H * W)]
for h in range(H):
    A = [int(i) - 1 for i in input().split()]
    for w in range(W):
        B[A[w]] = (h, w)

C = [0] * (H * W)
for i in range(D, H * W):
    h, w = B[i - D]
    nh, nw = B[i]
    C[i] = C[i - D] + abs(nh - h) + abs(nw - w)

Q = int(input())
for l, r in [[int(i) - 1 for i in input().split()] for _ in range(Q)]:
    print(C[r] - C[l])

Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = [int(i) for i in input().split()]
B = [(-1, -1) for _ in range(H * W)]
for h in range(H):
    A = [int(i) - 1 for i in input().split()]
    for w in range(W):
        B[A[w]] = (h, w)

Q = int(input())
for l, r in [[int(i) - 1 for i in input().split()] for _ in range(Q)]:
    su = 0
    C = B[l:r + 1:D]
    h, w = C[0]
    for nh, nw in C[1:]:
        su += abs(nh - h) + abs(nw - w)
        h, w = nh, nw
    print(su)


Fixed submission:
H, W, D = [int(i) for i in input().split()]
B = [(-1, -1) for _ in range(H * W)]
for h in range(H):
    A = [int(i) - 1 for i in input().split()]
    for w in range(W):
        B[A[w]] = (h, w)

C = [0] * (H * W)
for i in range(D, H * W):
    h, w = B[i - D]
    nh, nw = B[i]
    C[i] = C[i - D] + abs(nh - h) + abs(nw - w)

Q = int(input())
for l, r in [[int(i) - 1 for i in input().split()] for _ in range(Q)]:
    print(C[r] - C[l])
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    sc = iter(open(0).read().split())
    ni = lambda: int(next(sc))
    ns = lambda: next(sc)

    N, K = ni(), ni()

    K2 = K * 2
    A = [[0] * K2 for _ in range(K2)]
    for _ in range(N):
        x, y, c = ni(), ni(), ns()
        if c == "W":
            y += K
        A[y % K2][x % K2] += 1

    S = [[0] * (K2 + 1) for _ in range(K2 + 1)]
    for i in range(K2):
        for j in range(K2):
            S[i + 1][j + 1] = (
                A[i][j]
                + S[i + 1][j]
                + S[i][j + 1]
                - S[i][j]
            )

    ans = 0
    for i in range(K, K2 + 1):
        for j in range(K, K2 + 1):
            res = (
                S[i][j] + S[i - K][j - K] - S[i - K][j] - S[i][j - K]
                + S[i - K][j - K]
                + S[K2][j - K] - S[i][j - K]
                + S[i - K][K2] - S[i - K][j]
                + S[K2][K2] + S[i][j] - S[i][K2] - S[K2][j]
            )
            ans = max(ans, res, N - res)

    print(ans)

main()

Fixed submission:
sc = iter(open(0).read().split())
ni = lambda: int(next(sc))
ns = lambda: next(sc)

N, K = ni(), ni()

K2 = K * 2
A = [[0] * K2 for _ in range(K2)]
for _ in range(N):
    x, y, c = ni(), ni(), ns()
    if c == "W":
        y += K
    A[y % K2][x % K2] += 1

S = [[0] * (K2 + 1) for _ in range(K2 + 1)]
for i in range(K2):
    for j in range(K2):
        S[i + 1][j + 1] = (
            A[i][j]
            + S[i + 1][j]
            + S[i][j + 1]
            - S[i][j]
        )

ans = 0
for i in range(K, K2 + 1):
    for j in range(K, K2 + 1):
        res = (
            S[i][j] + S[i - K][j - K] - S[i - K][j] - S[i][j - K]
            + S[i - K][j - K]
            + S[K2][j - K] - S[i][j - K]
            + S[i - K][K2] - S[i - K][j]
            + S[K2][K2] + S[i][j] - S[i][K2] - S[K2][j]
        )
        ans = max(ans, res, N - res)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left

N = int(input())
A, B, C = (sorted([int(i) for i in input().split()]) for _ in range(3))

result = 0
for c in C:
    i = bisect_left(B, c)
    for b in B[:i]:
        j = bisect_left(A, b)
        result += j

print(result)

Fixed submission:
from bisect import bisect_left, bisect_right

N = int(input())
A, B, C = (sorted([int(i) for i in input().split()]) for _ in range(3))

print(sum(bisect_left(A, b) * (N - bisect_right(C, b)) for b in B))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        v = 4 * h * n - N * n - N * h
        if v == 0:
            continue
        w = (N * h * n) / v
        if w.is_integer() and w > 0:
            print(h, n, int(w))
            quit()

Fixed submission:
N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        v = 4 * h * n - N * n - N * h
        if v == 0:
            continue
        w = (N * h * n) / v
        if w.is_integer() and w > 0:
            print(h, n, int(w))
            quit()
Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import floyd_warshall

N, *A = map(int, open(0).read().split())
A = list(zip(*[iter(A)] * N))

B = floyd_warshall(A, False).astype(int)

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if A[i][j] > B[i][j]:
            print(-1)
            quit()

        if A[i][j] == B[i][j] and all(B[i][j] != B[i][k] + B[k][j] for k in range(N) if k != i and k != j):
            ans += B[i][j]

print(ans)

Fixed submission:
def WarshallFloyd(M):
    N = len(M)
    M = [m[:] for m in M]
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

N, *A = map(int, open(0).read().split())
A = list(map(list, zip(*[iter(A)] * N)))

B = WarshallFloyd(A)

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if A[i][j] > B[i][j]:
            print(-1)
            quit()

        if A[i][j] == B[i][j] and all(B[i][j] != B[i][k] + B[k][j] for k in range(N) if k != i and k != j):
            ans += B[i][j]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations

def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

INF = 1e10

N, M, K = map(int, input().split())
R = [int(i) - 1 for i in input().split()]
E = [[INF] * N for _ in range(N)]
for a, b, c in (map(int, input().split()) for _ in range(M)):
    a -= 1; b -= 1
    E[a][b] = E[b][a] = c

E = WarshallFloyd(E)
ans = min(sum(E[p[i]][p[i + 1]] for i in range(K - 1)) for p in permutations(R))
print(ans)


Fixed submission:
from itertools import permutations

def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

INF = 1e10

N, M, K = map(int, input().split())
R = [int(i) - 1 for i in input().split()]
E = [[INF] * N for _ in range(N)]
for a, b, c in (map(int, input().split()) for _ in range(M)):
    a -= 1; b -= 1
    E[a][b] = E[b][a] = c

E = WarshallFloyd(E)
ans = min(sum(E[p[i]][p[i + 1]] for i in range(K - 1)) for p in permutations(R))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations

def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

N, M, K = map(int, input().split())
R = [int(i) - 1 for i in input().split()]
E = [[0] * N for _ in range(N)]
for a, b, c in (map(int, input().split()) for _ in range(M)):
    a -= 1; b -= 1
    E[a][b] = E[b][a] = c

E = WarshallFloyd(E)
ans = min(sum(E[p[i]][p[i + 1]] for i in range(K - 1)) for p in permutations(R))
print(ans)


Fixed submission:
from itertools import permutations

def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

INF = 1e10

N, M, K = map(int, input().split())
R = [int(i) - 1 for i in input().split()]
E = [[INF] * N for _ in range(N)]
for a, b, c in (map(int, input().split()) for _ in range(M)):
    a -= 1; b -= 1
    E[a][b] = E[b][a] = c

E = WarshallFloyd(E)
ans = min(sum(E[p[i]][p[i + 1]] for i in range(K - 1)) for p in permutations(R))
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())

E = [[] for _ in range(N + 1)]
for a, b, c in [[int(i) for i in input().split()] for _ in range(N - 1)]:
    E[a].append((b, c))
    E[b].append((a, c))


Q, K = [int(i) for i in input().split()]
dist = [0] * (N + 1)
def dfs(cur, parent, d):
    dist[cur] = d
    for to, cost in E[cur]:
        if to == parent:
            continue
        dfs(to, cur, d + cost)
dfs(K, -1, 0)

for x, y in [[int(i) for i in input().split()] for _ in range(Q)]:
    print(dist[x] + dist[y])

Fixed submission:
import sys
sys.setrecursionlimit(100000)

N = int(input())

E = [[] for _ in range(N + 1)]
for a, b, c in [[int(i) for i in input().split()] for _ in range(N - 1)]:
    E[a].append((b, c))
    E[b].append((a, c))


Q, K = [int(i) for i in input().split()]
dist = [0] * (N + 1)
def dfs(cur, parent, d):
    dist[cur] = d
    for to, cost in E[cur]:
        if to == parent:
            continue
        dfs(to, cur, d + cost)
dfs(K, -1, 0)

for x, y in [[int(i) for i in input().split()] for _ in range(Q)]:
    print(dist[x] + dist[y])
Buggy python submission (verdict: Runtime Error):
from numpy import int64, divmod

N, A = open(0)
N, A = int(N), int64(A.split())

ans = 0
S = -1
while S:
    B, A = A % N, A // N
    S = B.sum()
    ans += S
    A += S - B

print(ans)


Fixed submission:
N, *A = map(int, open(0).read().split())

ans = 0
S = 1
while S:
    S = sum(a // N for a in A)
    ans += S
    A = [a + S - (a // N) * (N + 1) for a in A]

print(ans)

Buggy python submission (verdict: Runtime Error):
from numpy import int64, divmod

N, A = open(0)
N, A = int(N), int64(A.split())

ans = 0
S = -1
while S:
    B, A = divmod(A, N)
    S = B.sum()
    ans += S
    A += S - B

print(ans)


Fixed submission:
N, *A = map(int, open(0).read().split())

ans = 0
S = 1
while S:
    S = sum(a // N for a in A)
    ans += S
    A = [a + S - (a // N) * (N + 1) for a in A]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

def main():
    N, M, *L = map(int, open(0).read().split())

    E = [[] for _ in range(N + 1)]
    for a, b in zip(*[iter(L[:2 * M])] * 2):
        E[a].append(b)
        E[b].append(a)

    colors = [0] * (N + 1)
    visited = [False] * (N + 1)

    for v, d, c in reversed(tuple(zip(*[iter(L[2 * M + 1:])] * 3))):
        Q = deque([(d, v)])
        while Q:
            cnt, v = Q.popleft()
            if colors[v] == 0:
                colors[v] = c
            visited[v] = cnt
            if cnt > 0:
                Q.extend((cnt - 1, u) for u in E[v] if visited[u] < cnt)

    for c in colors[1:]:
        print(c)

if __name__ == '__main__':
    main()


Fixed submission:
from collections import deque

N, M, *L = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(L[:2 * M])] * 2):
    E[a].append(b)
    E[b].append(a)

colors = [0] * (N + 1)
visited = [-1] * (N + 1)

for v, d, c in reversed(tuple(zip(*[iter(L[2 * M + 1:])] * 3))):
    Q = deque([(d, v)])
    while Q:
        cnt, v = Q.popleft()
        if visited[v] >= cnt:
            continue
        if colors[v] == 0:
            colors[v] = c
        visited[v] = cnt
        if cnt > 0:
            Q.extend((cnt - 1, u) for u in E[v])

for c in colors[1:]:
    print(c)
Buggy python submission (verdict: Runtime Error):
def divisors(N):
    U = int(N ** 0.5)
    L = [i for i in range(1, U) if N % i == 0]
    C = [U] if M % U == 0 else []
    R = [N // r for r in reversed(L)]
    return L + C + R

N, M = map(int, input().split())
print(max(d for d in divisors(M) if d * N <= M))


Fixed submission:
def combinations(N):
    comb = [[0] * (N + 1) for _ in range(N + 1)]
    comb[0][0] = 1
    for i in range(1, N + 1):
        for j in range(i + 1):
            comb[i][j] += comb[i - 1][j]
            if j > 0:
                comb[i][j] += comb[i - 1][j - 1]
    return comb


nCk = combinations(60)

N, A, B, *V = map(int, open(0).read().split())

V.sort(reverse=True)

num = V.count(V[A - 1])

ans = 0
if V[0] == V[A - 1]:
    for i in range(A, B + 1):
        ans += nCk[num][i]
else:
    a = V[:A].count(V[A - 1])
    ans = nCk[num][a]

ave = sum(V[:A]) / A

print("{:.9f}".format(ave))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
i=input
i()
a=s=1
for x in i().split():
 a*=s
 if 2*~-s<int(x):s+=1
print(a%(10**9+7))

Fixed submission:
mod = 10 ** 9 + 7

N, *X = map(int, open(0).read().split())

stack = []
ans = 1
for x in X:
    stack.append(x)
    if x < 2 * len(stack) - 1:
        ans = (ans * len(stack)) % mod
        stack.pop()
    else:
        ans = (ans * len(stack)) % mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
i=input
i()
a=s=1
for x in i().split():
 a*=s
 if 2*~-s<int(x):s+=1
print(a%(10**9+7))

Fixed submission:
mod = 10 ** 9 + 7

N, *X = map(int, open(0).read().split())

stack = []
ans = 1
for x in X:
    stack.append(x)
    if x < 2 * len(stack) - 1:
        ans = (ans * len(stack)) % mod
        stack.pop()
    else:
        ans = (ans * len(stack)) % mod

print(ans)
Buggy python submission (verdict: Runtime Error):
N, *A = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for i, v in enumerate(A, 1):
    E[v - 1].append(i)

def dfs(v):
    D = sorted(dfs(u) for u in E[v])
    return max([0] + [len(D) - i + d for i, d in enumerate(D)])

print(dfs(0))

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)

N, *A = map(int, open(0))

E = [[] for _ in [0] + A]
for i, v in enumerate(A, 1):
    E[v - 1] += i,

def dfs(v):
    D = sorted(map(dfs, E[v]))
    l = len(D)
    return max([0] + [l - i + d for i, d in enumerate(D)])

print(dfs(0))
Buggy python submission (verdict: Time Limit Exceeded):
N,*E=map(int,open(0).read().split())
E=sorted((e,2*(i<N)-1)for i,e in enumerate(E))
a,c=1,0
for _,d in E:
	if c*d<0:a*=abs(c)
	c+=d
print(a%(10**9+7))

Fixed submission:
mod = 10 ** 9 + 7
INF = 10 ** 10

N = int(input())
A = [int(input()) for _ in range(N)] + [INF]
B = [int(input()) for _ in range(N)] + [INF]

A.sort()
B.sort()

ans = 1
a = b = 0
i = j = 0
while i < N or j < N:
    if A[i] < B[j]:
        if b > 0:
            ans *= b
            b -= 1
        else:
            a += 1
        i += 1
    else:
        if a > 0:
            ans *= a
            a -= 1
        else:
            b += 1
        j += 1

    ans %= mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,*E=map(int,open(0).read().split())
a,c=1,0
for _,d in sorted((e,2*(i<N)-1)for i,e in enumerate(E)):
	if c*d<0:a*=abs(c)
	c+=d
print(a%(10**9+7))

Fixed submission:
mod = 10 ** 9 + 7
INF = 10 ** 10

N = int(input())
A = [int(input()) for _ in range(N)] + [INF]
B = [int(input()) for _ in range(N)] + [INF]

A.sort()
B.sort()

ans = 1
a = b = 0
i = j = 0
while i < N or j < N:
    if A[i] < B[j]:
        if b > 0:
            ans *= b
            b -= 1
        else:
            a += 1
        i += 1
    else:
        if a > 0:
            ans *= a
            a -= 1
        else:
            b += 1
        j += 1

    ans %= mod

print(ans)