Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

h,w,k = map(int, input().split())
item = [[0 for _ in range(w)] for _ in range(h)]
for i in range(k):
    y,x,v = list(map(int,input().split()))
    item[y-1][x-1]=v

dp = [[[0 for _ in range(4)] for _ in range(w)] for _ in range(h)]

for y in range(h):
    for x in range(w):
        for i in range(4):
            if y<h-1:
                dp[y+1][x][0]=max(dp[y+1][x][0],dp[y][x][i])
            if x<w-1:
                dp[y][x+1][i]=max(dp[y][x+1][i],dp[y][x][i])

        if item[y][x]>0:
            for i in range(3):
                if y<h-1:
                    dp[y+1][x][0]=max(dp[y+1][x][0],dp[y][x][i] + item[y][x])
                if x<w-1:
                    dp[y][x+1][i+1]=max(dp[y][x+1][i+1],dp[y][x][i] + item[y][x])


if item[-1][-1] != 0:
    for i in range(3):
        dp[-1][-1][i] += item[-1][-1]

ans=max(dp[-1][-1])

print(ans)

### FIXED CODE ###

h,w,k = map(int, input().split())
item = [[0 for _ in range(w)] for _ in range(h)]
for i in range(k):
    y,x,v = list(map(int,input().split()))
    item[y-1][x-1]=v

dp = [[[0 for _ in range(w)] for _ in range(h)] for _ in range(4)]

for y in range(h):
    for x in range(w):
        for i in range(4):
            if y<h-1:
                dp[0][y+1][x]=max(dp[0][y+1][x],dp[i][y][x])
            if x<w-1:
                dp[i][y][x+1]=max(dp[i][y][x+1],dp[i][y][x])

        if item[y][x]>0:
            for i in range(3):
                if y<h-1:
                    dp[0][y+1][x]=max(dp[0][y+1][x],dp[i][y][x] + item[y][x])
                if x<w-1:
                    dp[i+1][y][x+1]=max(dp[i+1][y][x+1],dp[i][y][x] + item[y][x])

ans=[dp[0][-1][-1] + item[-1][-1],
     dp[1][-1][-1] + item[-1][-1],
     dp[2][-1][-1] + item[-1][-1],
     dp[3][-1][-1]]
print(max(ans))
### BUGGY CODE ###

_,C,*I=[list(map(int,o.split()))for o in open(0)]
for d,q in I[731:]:
 I[d+364][0]=q;L=[0]*26;R=P=0
 for i in range(365):t=I[i+365][0]-1;P+=sum(C)-(i+1-L[t])*C[t];R+=I[i][t]-P;L[t]=i+1
 print(R)

### FIXED CODE ###

def P(s):
  L = [0] * 26
  R = P = 0
  for i in range(D):
    t = I[i + D][0] - 1
    R += I[i][t]
    P += s - (i + 1 - L[t]) * C[t]
    R -= P
    L[t] = i + 1
  return R
(D,), C, *I = [list(map(int, o.split())) for o in open(0)]
for d, q in I[2*D + 1:]:
  I[d - 1 + D][0] = q
  print(P(sum(C)))
### BUGGY CODE ###

a,b,x = map(int,input().split())
count =0
for i in range(a,b+1):
  if i%x ==0:
    count += 1
print(count)
    

### FIXED CODE ###

a,b,x = map(int,input().split())
print(int(b//x)-int((a-1)//x))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5 + 1)
n, m = map(int, input().split())

graph = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())

    graph[a].append(b)
    graph[b].append(a)

rooted = [[] for _ in range(n)]
rev_rooted = [[] for _ in range(n)]
que = [(0, -1)]
while que:
    node, parent = que.pop()
    for child in graph[node]:
        if child != parent:
            que.append((child, node))
            rooted[node].append(child)
            rev_rooted[child].append(node)

def mod(v):
    if v >= m:
        return v % m
    return v

dp = [None] * n
def dfs(node):
    if dp[node] is not None:
        return dp[node]

    pattern = 1 # 自身のみのパターン
    for child in rooted[node]:
        pattern = mod(pattern * (dfs(child) + 1))
    dp[node] = pattern
    return pattern

rev_dp = [None] * n
def rev_dfs(node):
    if rev_dp[node] is not None:
        return rev_dp[node]

    pattern = 1 # 自身のみのパターン
    if not rev_rooted[node]:
        pattern = 0
    for parent in rev_rooted[node]: # 親は0or1人
        pattern = mod(pattern * (rev_dfs(parent) + 1))
        for child in rooted[parent]:
            if child != node:
                pattern = mod(pattern * (dfs(child) + 1))
    rev_dp[node] = pattern
    return pattern

# print("-----")
for i in range(n):
    print(mod(dfs(i) * (rev_dfs(i) + 1)))


### FIXED CODE ###

import itertools
import sys
import heapq
sys.setrecursionlimit(10**5 + 1)
n, m = map(int, input().split())

graph = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())

    graph[a].append(b)
    graph[b].append(a)

rooted = [[] for _ in range(n)]
rev_rooted = [[] for _ in range(n)]
que = [(0, -1, 0)]
bfs_target = []
while que:
    node, parent, distance = que.pop()
    heapq.heappush(bfs_target, (-distance, node))
    for child in graph[node]:
        if child != parent:
            que.append((child, node, distance + 1))
            rooted[node].append(child)
            rev_rooted[child].append(node)
            # print(node, child)

def mod(v):
    if v >= m:
        return v % m
    return v


dp = [1] * n
while bfs_target:
    node = heapq.heappop(bfs_target)[1]
    for parent in rev_rooted[node]:
        dp[parent] = mod(dp[parent] * (dp[node] + 1))
        que.append(parent)

rev_dp = [0] * n
que = [0]
while que:
    node = que.pop()
    cp = [1]
    rev_cp = [1]
    for i, child in enumerate(rooted[node]):
        cp.append(mod(cp[i] * (dp[child] + 1)))
    for i, child in enumerate(reversed(rooted[node])):
        rev_cp.append(mod(rev_cp[i] * (dp[child] + 1)))
    rev_cp = rev_cp[::-1]
    for i, child in enumerate(rooted[node]):
        rev_dp[child] = mod(cp[i] * rev_cp[i + 1] * (rev_dp[node] + 1))
        que.append(child)


# print(dp)
for v1, v2 in zip(dp, rev_dp):
    print(mod(v1 * (v2 + 1)))
### BUGGY CODE ###

def Calculator(K):
    a =[0]*K
    a[0] = 7
    if a[0] % K == 0:
        return (1)
    for i in range(1,K):
        a[i] = 10 * a[i-1] + 7
        if a[i] % K == 0:
            return (i+1)
    return -1
K = int(input())
print(Calculator(K))

### FIXED CODE ###

K = int(input())
a = 7
for i in range(K):
    if a % K == 0:
        print(i+1)
        exit()
    a = (10 * a + 7) % K
print(-1)
### BUGGY CODE ###

h,w,m=map(int,input().split())
r=dict()
c=dict()
pos=[]
rmax=0
cmax=0
for i in range(m):
    row,col=map(int,input().split())
    if(row in r):
        r[row]+=1
        rmax=max(r[row],rmax)
    else:
        r[row]=1
        rmax=max(r[row],rmax)
    if(col in c):
        c[col]+=1
        cmax=max(c[col],cmax)
    else:
        c[col]=1
        cmax=max(c[col],cmax)
    pos.append(str(row)+str(col))
    
sorted(r.items(),key=lambda x:x[1])
sorted(c.items(),key=lambda x:x[1])
ans=-100
for i in r.keys():
    if(r[i]<rmax):
        continue
    for j in c.keys():
        if(c[j]<cmax):
            continue
        tmp=r[i]+c[j]
        if((str(i)+str(j)) in pos):
            tmp-=1
        ans=max(ans,tmp)
        
print(ans)

### FIXED CODE ###

h,w,m=map(int,input().split())
row=[0 for i in range(h)]
col=[0 for i in range(w)]
a=[]
for i in range(m):
    r,c=map(lambda x:int(x)-1,input().split())
    a.append([r,c])
    row[r]+=1
    col[c]+=1
rmax=max(row)
cmax=max(col)
ans=rmax+cmax
flag=row.count(rmax)*col.count(cmax)
for i,j in a:
    if(row[i]==rmax and col[j]==cmax):
        flag-=1
if(flag==0):
    ans-=1
print(ans)
### BUGGY CODE ###

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

for i in range(n):
    a=int(input())
    b.append(a)

for i in range(n):
    c=b[:i]+b[i+1:]
    print(max(c))
    

### FIXED CODE ###

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

for i in range(n):
    a=int(input())
    b.append(a)
    
c=sorted(b,reverse=True)    
for i in range(n):
    if b[i]==c[0]:
        print(c[1])
    else:
        print(c[0])
### BUGGY CODE ###

def resolve():
    N, K, Q = list(map(int, input().split()))
    A = [int(input()) for _ in range(Q)]
    points = [K] * N
    for i in range(N):
        points[i] += A.count(i+1)

    points = list(map(lambda x: x - Q, points))

    for i in points:
        if i > 0:
            print('Yes')
        else:
            print('No')
    return

resolve()

### FIXED CODE ###

def resolve():
    N, K, Q = list(map(int, input().split()))
    A = [int(input()) for _ in range(Q)]
    points = [0] * N
    for i in range(Q):
        points[A[i]-1] += 1

    for i in range(N):
        if K + points[i] - Q > 0:
            print('Yes')
        else:
            print('No')

    return

resolve()
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
inf = float("inf")
s = [["#"] * (W + 2)]
D = [[inf] * (W + 2)]
white_num = 0
for i in range(H):
    main = list(input())
    white_num += len([e for e in main if e == "."])
    s.append(["#"] + main + ["#"])
    D.append([inf] * (W + 2))
s.append(["#"] * (W + 2))
D.append([inf] * (W + 2))
visited = [[False] * (W + 2) for i in range(H + 2)]


def BFS():  # 幅優先探索(inf=>キュー=>訪問)
    global D
    D[1][1] = 1
    q = deque()
    q.append((1, 1))
    while len(q) != 0:
        p = q.popleft()
        visited[p[0]][p[1]] = True
        if p == (H, W):  # ゴールを訪問したら全部終わってなくても打ち切る
            return D[H][W]
        for e in [(p[0] + 1, p[1]), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0], p[1] - 1)]:
            if s[e[0]][e[1]] == "." and not visited[e[0]][e[1]]:
                D[e[0]][e[1]] = min(D[p[0]][p[1]] + 1, D[e[0]][e[1]])
                q.append(e)
    return D[H][W]


white_min = BFS()

# for i in range(1, H + 1):
#    print(" ".join(list(map(str, D[i][1:-1]))))

if white_min == inf:
    print(-1)
else:
    print(white_num - white_min)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
inf = float("inf")
s = [["#"] * (W + 2)]
D = [[inf] * (W + 2)]
white_num = 0
for i in range(H):
    main = list(input())
    white_num += len([e for e in main if e == "."])
    s.append(["#"] + main + ["#"])
    D.append([inf] * (W + 2))
s.append(["#"] * (W + 2))
D.append([inf] * (W + 2))


def BFS():  # 幅優先探索
    global D
    D[1][1] = 1
    q = deque()
    q.append((1, 1))
    while len(q) != 0:
        p = q.popleft()
        for e in [(p[0] + 1, p[1]), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0], p[1] - 1)]:
            if s[e[0]][e[1]] == "." and D[e[0]][e[1]] == inf:
                D[e[0]][e[1]] = D[p[0]][p[1]] + 1
                q.append(e)
                if e == (H, W):
                    return white_num - D[H][W]
    return -1


print(BFS())

# for i in range(1, H + 1):
#    print(" ".join(list(map(str, D[i][1:-1]))))
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
N, K = map(int, input().split())

H = deque(list(map(int, input().split())))
max_K = 100
for _ in range(max_K):
  H.append(float('inf'))

dp = [float('inf')] * (N + max_K)
dp[0] = 0

for n in range(N):
  for offset in range(1, K + 1):
    cost = dp[n] + abs(H[n] - H[n + offset])
    if (dp[n + offset] > cost):
      dp[n + offset] = cost

print(dp[N - 1])


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().split())

# H = deque(list(map(int, input().split())))
max_K = 100
H = list(map(int, input().split()))
H += [0] * max_K
# for _ in range(max_K):
#   H.append(0)

dp = [float('inf')] * (N + max_K)
dp[0] = 0

for n in range(N):
  for offset in range(1, K + 1):
    new_index = n + offset
    cost = dp[n] + abs(H[n] - H[new_index])
    if (dp[new_index] > cost):
      dp[new_index] = cost

print(dp[N - 1])
### BUGGY CODE ###

import sys
from bisect import bisect_left
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
A = sorted([int(x) for x in input().strip().split()])
BC = [0] * M

for m in range(M):
    BC[m] = tuple([int(x) for x in input().strip().split()])

BC.sort(reverse=True, key=lambda x: x[1])

offset = 0
ans = 0
for i, bc in enumerate(BC):
    if offset >= len(A):
        break
    if bc[1] >= A[min(offset+bc[0]-1, len(A)-1)]:
        ans += min(bc[0], len(A[offset:])) * bc[1]
        offset += bc[0]
        continue
    elif bc[1] <= A[offset]:
        ans += sum(A[offset:])
        break
    else:
        c = 0
        while bc[1] >= A[offset+c]:
            ans += bc[1]
            c += 1
        else:
            offset += c
else:
    if offset < len(A):
        ans += sum(A[offset:])
print(ans)

### FIXED CODE ###

import sys
from bisect import bisect_left
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
A = sorted([int(x) for x in input().strip().split()])
BC = [0] * M

for m in range(M):
    BC[m] = tuple([int(x) for x in input().strip().split()])

BC.sort(reverse=True, key=lambda x: x[1])

offset = 0
ans = 0
for i, bc in enumerate(BC):
    if offset >= len(A):
        break
    if bc[1] >= A[min(offset+bc[0]-1, len(A)-1)]:
        ans += min(bc[0], N - offset) * bc[1]
        offset += bc[0]
        continue
    elif bc[1] <= A[offset]:
        ans += sum(A[offset:])
        break
    else:
        c = 0
        while bc[1] >= A[offset+c]:
            ans += bc[1]
            c += 1
        else:
            offset += c
else:
    if offset < len(A):
        ans += sum(A[offset:])
print(ans)
### BUGGY CODE ###

# C - 高橋君とカード / Tak and Cards

#import numpy as np
import math

N, A = map(int, input().split())
x = list(map(int, input().split()))

# 数列aと整数Aを与えると、aからいくつか取って合計Aにするパターンが何通りあるかを返す関数
def partial_sum(a,A):
    n = len(a)
    dp = [[0]*(A+2) for _ in range(n+2)] # dp[i+1][j] a[i]までの数からいくつか選んで総和をjにするパターンの数
    dp[0][0] = 1
    
    for i in range(n):
        for j in range(A+1):
            if j >= a[i]:
                dp[i+1][j] = dp[i][j-a[i]] + dp[i][j]
            else:
                dp[i+1][j] = dp[i][j]
                
    return dp[n][A]

x_diff = [a - A for a in x] # ここから合計0になるように取る。負の数列についてpartial_sumが動かないことに注意
x_diff_negative = [-a for a in x_diff if a < 0]
x_diff_positive = [a for a in x_diff if a > 0]

ans = 0
for i in range(1, min(sum(x_diff_negative), sum(x_diff_positive)) + 1):
    ans += partial_sum(x_diff_negative,i) * partial_sum(x_diff_positive,i) 

# 0の選び方
n_pattern_0 = 0
n_0 = x_diff.count(0)
if n_0 > 0:
    for i in range(1, n_0+1):
        n_pattern_0 += math.factorial(n_0) // (math.factorial(n_0-i) * math.factorial(i))

# ここまで数えた全てのパターンそれぞれについて、x_diff中の0をいくつか含めた別パターンがある
# 0単体で選ぶ方法もある
ans += (ans+1) * n_pattern_0
    
print(ans)

### FIXED CODE ###

# C - 高橋君とカード / Tak and Cards

#import numpy as np
import math

N, A = map(int, input().split())
x = list(map(int, input().split()))

# 数列aと整数Aを与えると、aからいくつか取って合計Aにするパターンが何通りあるかを返す関数
def partial_sum(a,A):
    n = len(a)
    dp = [[0]*(A+2) for _ in range(n+2)] # dp[i+1][j] a[i]までの数からいくつか選んで総和をjにするパターンの数
    dp[0][0] = 1
    
    for i in range(n):
        for j in range(A+1):
            if j >= a[i]:
                dp[i+1][j] = dp[i][j-a[i]] + dp[i][j]
            else:
                dp[i+1][j] = dp[i][j]
                
    return dp[n][A]

x_diff = [a - A for a in x] # ここから合計0になるように取る。負の数列についてpartial_sumが動かないことに注意
x_diff_negative = [-a for a in x_diff if a < 0]
x_diff_positive = [a for a in x_diff if a > 0]

ans = 0
for i in range(1, min(sum(x_diff_negative), sum(x_diff_positive)) + 1):
    ans += partial_sum(x_diff_negative,i) * partial_sum(x_diff_positive,i) 

# 0の選び方
n_pattern_0 = 0
n_0 = x_diff.count(0)
if n_0 > 0:
    for i in range(1, n_0+1):
        n_pattern_0 += math.factorial(n_0) // (math.factorial(n_0-i) * math.factorial(i))

# ここまで数えた全てのパターンそれぞれについて、x_diff中の0をいくつか含めた別パターンがある
# 0単体で選ぶ方法もある
ans += (ans+1) * n_pattern_0
    
print(ans)
### BUGGY CODE ###

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"

s = v()
q = k()
q_list = deque(L() for i in range(q))

while q_list:
    a = q_list.popleft()
    a = deque(a)
    while a:
        b = a.popleft()
        if b == "1":
            s = s[::-1]
        else:
            c = a.popleft()
            d = a.popleft()
            if c == "1":
                s = d+s
            else:
                s = s+d

print(s)             

### FIXED CODE ###

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

s = deque(X())
n = k()
normal = 0
for i in range(n):
  a = input().split()
  if int(a[0]) == 1:
    normal ^= 1
  else:
    k = int(a[1]) - 1
    k ^= normal
    if k == 1:
      s.append(a[2])
    else:
      s.appendleft(a[2])
print(''.join(s) if normal == 0 else ''.join(list(s)[::-1]))
### BUGGY CODE ###

def calculate_happiness(S: str, N: int) -> int:
  if N == 1:
    return 0
  happiness = 0
  if S[0] == S[1] == 'R':
    happiness += 1
  if S[-1] == S[-2] == 'L':
    happiness += 1
  for i in range(1, N-1):
    if S[i] == S[i+1] == 'R':
      happiness += 1
    elif S[i] == S[i-1] == 'L':
      happiness += 1
  return happiness
 
def change_string(S: str, l: int, r: int) -> str:
  part = S[l:r+1][::-1].replace('R', '_')
  part = part.replace('L', 'R').replace('_', 'L')
  return S[:l] + part + S[r+1:]
 
N, K = list(map(int, input().split()))
S = input()
happiness = calculate_happiness(S, N)
opt_S = S
opt_happiness = happiness
for k in range(K):
  S = opt_S
  for l in range(N-1):
    for r in range(l+1, N):
      new_S = change_string(S, l, r)
      happiness = calculate_happiness(new_S, N)
      if happiness > opt_happiness:
        opt_S = new_S
        opt_happiness = happiness
print(opt_happiness)

### FIXED CODE ###

N, K = list(map(int, input().split()))
S = input()

happy = 0
for i in range(N-1):
  if S[i] == S[i+1]:
    happy += 1
print(min([N-1, happy + 2 * K]))
### BUGGY CODE ###

import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()


if __name__ == "__main__":
    H, W = map(int, input().split())
    ch, cw = map(lambda x: int(x)-1, input().split())
    dh, dw = map(lambda x: int(x)-1, input().split())
    maze = [list(input()) for _ in range(H)]
    INF = 10**8
    mc = [[INF]*W for _ in range(H)]
    walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    warp = [
        (2, 2), (2, 1), (2, 0), (2, -1), (2, -2),
        (1, 2), (1, 1), (1, -1), (1, -2),
        (0, 2), (0, -2),
        (-1, 2), (-1, 1), (-1, -1), (-1, -2),
        (-2, 2), (-2, 1), (-2, 0), (-2, -1), (-2, -2)
    ]
    walk_que = deque()
    warp_que = deque()
    walk_que.append((ch, cw, 0))
    while walk_que:
        y, x, w = walk_que.popleft()
        mc[y][x] = w
        if y == dh and x == dw:
            break
        exit_wall = False
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] == INF:
                if maze[ny][nx] == ".":
                    walk_que.append((ny, nx, w))
                else:
                    exit_wall = True
        if exit_wall:
            warp_que.append((y, x, w))
        if not walk_que:
            while warp_que:
                y, x, w = warp_que.popleft()
                for dy, dx in warp:
                    ny = y + dy
                    nx = x + dx
                    if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] == INF and maze[ny][nx] == ".":
                        walk_que.append((ny, nx, w+1))
    if mc[dh][dw] == INF:
        print(-1)
    else:
        print(mc[dh][dw])


### FIXED CODE ###

import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()


if __name__ == "__main__":
    H, W = map(int, input().split())
    ch, cw = map(lambda x: int(x)-1, input().split())
    dh, dw = map(lambda x: int(x)-1, input().split())
    maze = [list(input()) for _ in range(H)]
    INF = 10**8
    mc = [[INF]*W for _ in range(H)]
    mc[ch][cw] = 0
    walk_que = deque()
    walk_que.append((ch, cw, 0))
    while walk_que:
        y, x, w = walk_que.popleft()
        for ny, nx in [(y+1, x), (y-1, x), (y, x+1), (y, x-1)]:
            if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] > w and maze[ny][nx] == ".":
                mc[ny][nx] = w
                walk_que.appendleft((ny, nx, w))
        for dy in range(-2, 3):
            ny = y + dy
            for dx in range(-2, 3):
                nx = x + dx
                if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] > w+1 and maze[ny][nx] == ".":
                    mc[ny][nx] = w + 1
                    walk_que.append((ny, nx, w+1))
    if mc[dh][dw] == INF:
        print(-1)
    else:
        print(mc[dh][dw])
### BUGGY CODE ###

from collections import Counter

n = int(input())
xs = [None] + [int(input())-1 for _ in range(n-1)]

count_win = Counter(xs)
q = [i for i in range(n) if not i in count_win]
children = [[] for i in range(n)]

while not q[0]==0:
    i = q.pop(0)
    children[i].sort(reverse=True)
    children[i] = max(v+w for v, w in  enumerate([0]+children[i]))
    j = xs[i]
    children[j].append(children[i])
    if count_win[j] <= 1:
        q.append(j)
    else:
        count_win[j] -= 1

children[0].sort(reverse=True)
children[0] = max(v+w for v, w in  enumerate([0]+children[0]))

print(children[0])

### FIXED CODE ###

from collections import Counter

n = int(input())
xs = [None] + [int(input())-1 for _ in range(n-1)]

count_win = Counter(xs)
q = [i for i in range(n) if not i in count_win]
children = [[] for i in range(n)]

qi = 0
while not q[qi]==0:
    i, qi = q[qi], qi+1
    children[i].sort(reverse=True)
    children[i] = max(v+w for v, w in  enumerate([0]+children[i]))
    j = xs[i]
    children[j].append(children[i])
    if count_win[j] <= 1:
        q.append(j)
    else:
        count_win[j] -= 1

children[0].sort(reverse=True)
children[0] = max(v+w for v, w in  enumerate([0]+children[0]))

print(children[0])
### BUGGY CODE ###

n = int(input())
ans = 0
lis = []
for i in range(n):
    s = input()
    s_lis = [s[j] for j in range(10)]
    lis.append(s_lis)
for i in range(n-1):
    for j in range(i+1,n):
        same = True
        for k in range(10):
            if lis[i][k] in lis[j]  and lis[i].count(lis[i][k]) == lis[j].count(lis[i][k]):
                continue
            else:
                same = False
                break
        if same == True:
            ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
ans = 0
dic = {}
for i in range(n):
    sorted_s = sorted(input())
    s = ""
    for j in range(10):
        s = s + sorted_s[j]
    
    if s not in dic:
        dic[s] = 1
    else:
        ans += dic[s]
        dic[s] = dic[s] + 1
print(ans)
### BUGGY CODE ###

n = int(input())
x = tuple(map(int,input().split()))
x_sort = sorted(x,reverse=True)
for i in range(n):
    print(x_sort[n//2] if x_sort.index(x[i]) < n//2 else x_sort[n//2-1])

### FIXED CODE ###

n = int(input())
x = tuple(map(int,input().split()))
x_sort = sorted(x,reverse=True)
x_median = x_sort[n//2-1]
x_median2 = x_sort[n//2]
for i in range(n):
    print(x_median2 if x[i] > x_median2 else x_median)
### BUGGY CODE ###

k,e=map(int,input().split())
ans=0
for s in range(k+1):
  for t in range(k+1):
    for r in range(k+1):
      if s+t+r==e:ans+=1
print(ans)

### FIXED CODE ###

ans=0
a,b=map(int,input().split())
for s in range(a+1):
    for t in range(a+1):
        if 0<=b-s-t<=a:
            ans+=1
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
ans = n-1
for i in range(n):
    ans = min(ans, s[:i].count('W')+s[i:].count('E'))
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = n-1
r = s.count('E')
for i in range(n):
    if s[i] == 'E':
        r -= 1
    ans = min(ans, r)
    if s[i] == 'W':
        r += 1
print(ans)