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

n, u, v = map(int, input().split())
V = [ [] for _ in range(n + 1) ]
for _ in range(n - 1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

t, a = 0, 0
tpos, apos = {u:0}, {v:0}

amin = float("-inf")
while len(tpos) > 0:
    t_new = dict() # T moves                                                                                                                            
    for k, v in tpos.items():
        for dst in V[k]:
            t_new[dst] = max(t_new.get(dst, 0), v + 1)
            if dst in apos:
                amin = max(amin, apos[dst])
                del t_new[dst]

    a_new = dict() # A moves                                                                                                                            
    for k, v in apos.items():
        for dst in V[k]:
            a_new[dst] = max(a_new.get(dst, 0), v + 1)
            if dst in t_new:
                amin = max(amin, a_new[dst])
                del t_new[dst]

    tpos = t_new
    apos = a_new

print(amin)


### FIXED CODE ###

n, u, v = map(int, input().split())
V = [ [] for _ in range(n + 1) ]
for _ in range(n - 1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

import collections

def bfs(x):
    X = [ -1 ] * (n + 1)
    q = collections.deque([ (x, 0) ])
    X[x] = 0
    while q:
        node, dist = q.popleft()
        for dst in V[node]:
            if X[dst] == -1:
                X[dst] = dist + 1
                q.append((dst, dist + 1))
    return X

T = bfs(u)
A = bfs(v)

ans = 0
for i in range(1, len(T)):
    if T[i] < A[i]:
        ans = max(ans, A[i] - 1)
print(ans)
### BUGGY CODE ###

import math

def sosuucheck(val):
    flg = True
    max_search = math.ceil(math.sqrt(val))
    if val <= 3:
        pass
    else:
        for i in range(2, max_search+1):
            if val % i == 0:
                flg = False
                break
    return flg

def yakusuu(a):
    t = []
    for i in range(1,a+1):
        if a%i==0:
            t.append(i)
    return t

def kouyakusuu(a,b):
    t = []
    u = 0
    d = 0
    if a>b:
        u = a
        d = b
    else:
        u = b
        d = a
    for i in range(1,d+1):
        if u%i==0 and d%i==0:
            t.append(i)
    return t

a,b = map(int,input().split())

#t = list(map(yakusuu,kouyakusuu(a,b)))
t = kouyakusuu(a,b)
sn = 0
for i in t:
    if sosuucheck(i):
        sn += 1


print(sn)

### FIXED CODE ###

import math

A, B = [int(item) for item in input().split()]

def gdc(A, B):
    if B == 0:
        return A
    else:
        return gdc(B, A % B)

def chk_pn(num):
    flag = True
    if num  <= 3:
        pass
    else:
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                flag = False
                break
    return flag

def mk_factor(num):
    max_divisor = int(math.sqrt(num))+1
    divisor = 2
    factor_list = [1]

    while divisor <= max_divisor:
        if num % divisor == 0:
            factor_list.append(divisor)
            num /= divisor
        else:
            divisor += 1
    if num != 1.0:
        factor_list.append(num)
    return factor_list

GDC = gdc(A, B)
#pn_factor = [i for i in mk_factor(GDC) if chk_pn(i) is True]

print(len(set(mk_factor(GDC))))
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

class Node:
    def __init__(self):
        self.size = 1  # 自分以下のノードの数
        self.children = []

def dfs(v):
    V = Node()
    visited[v] = True
    for u in AL[v]:
        if visited[u]: continue
        U = dfs(u)
        V.size += U.size
        V.children.append(U)
    return V

def anaaki(V):
    ret = pow(2, n - 1, p) - 1
    for ch in V.children:
        ret -= pow(2, ch.size, p) - 1
        ret %= p
    ret -= pow(2, n - V.size, p) - 1
    ret %= p
    return ret

n = int(input())
AL = [[] for _ in range(n)]
visited = [False] * n
p = 10 ** 9 + 7
for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    AL[a].append(b)
    AL[b].append(a)

# dfs
root = dfs(0)
que = deque([root])
numer = 0
while que:
    next = que.popleft()
    numer += anaaki(next)
    numer %= p
    for ch in next.children:
        que.append(ch)

denom = pow(2, n, p)

print( numer * pow(denom, p - 2, p) % p)

### FIXED CODE ###

# classを使うのをやめてlistで実施する
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
import sys
input = sys.stdin.readline

def dfs(v):
    visited[v] = True
    for i in range(len(AL[v][CHILDREN])):
        u = AL[v][CHILDREN][i]
        if visited[u]:
            AL[v][CHILDREN][i] = None
            continue
        AL[v][SIZE] += dfs(u)
    return AL[v][SIZE]


def anaaki(v):
    ret = powp - 1
    for ch in AL[v][CHILDREN]:
        if ch is None: continue
        ret -= pow(2, AL[ch][SIZE], p) - 1
        ret %= p
    ret -= pow(2, n - AL[v][SIZE], p) - 1
    ret %= p
    return ret

n = int(input())
SIZE = 0
CHILDREN = 1
AL = [[1, []] for _ in range(n)]
visited = [False] * n
p = 10 ** 9 + 7
powp = pow(2, n - 1, p)

for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    AL[a][CHILDREN].append(b)
    AL[b][CHILDREN].append(a)

dfs(0)
numer = 0
for i in range(n):
    numer += anaaki(i)
    numer %= p

denom = pow(2, n, p)
print(numer * pow(denom, p - 2, p) % p)
### BUGGY CODE ###

MOD = 10**9 + 7
s = input()[::-1]
n = len(s)
dp = [0 for _ in range(13)]
dp[0] = 1
for i in range(n):
	dpp = [0 for _ in range(13)]
	if s[i] != "?":
		for j in range(13):
			dpp[(j + (10**i)*int(s[i])) % 13] = dp[j]
	else:
		for j in range(13):
			for k in range(10):
				dpp[(j + (10**i)*k) % 13] += dp[j]
	dp = [dppp%MOD for dppp in dpp]
print(dp[5])

### FIXED CODE ###

MOD = 10**9 + 7
s = input()
n = len(s)
dp = [0 for _ in range(13)]
dp[0] = 1
for i in range(n):
	dpp = [0 for _ in range(13)]
	if s[i] != "?":
		for j in range(13):
			dpp[(j*10+int(s[i])) % 13] = dp[j]
	else:
		for j in range(13):
			for k in range(10):
				dpp[(j*10+k)%13] += dp[j]
				dpp[(j*10+k)%13] %= MOD
	dp = dpp
print(dp[5])
### BUGGY CODE ###

NK = input().split()
N,K = int(NK[0]),int(NK[1])
N = list(map(int,input().split()))
if K != 0 and len(N) < K:
    print(0)
    exit()
for i in range(K):
    N.remove(max(N))
print(sum(N))

### FIXED CODE ###

import sys
NK = input().split()
N,K = int(NK[0]),int(NK[1])
H = list(map(int,input().split()))
if K != 0 and len(H) < K:
    print(0)
    exit()
H.sort()
for i in range(K):
    H.pop(-1)
print(sum(H))

def input():
    return sys.stdin.readline()[:-1]
### BUGGY CODE ###

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

s=[]
g=[]
for i, j in ab:
    if i==1:
        s.append(j)
    elif j==1:
        s.append(i)
    elif i==N:
        g.append(j)
    elif j==N:
        g.append(i)
flag=0
for i in range(len(s)):
    if s[i] in g:
        flag=1
        break

print("POSSIBLE"  if flag else "IMPOSSIBLE")


### FIXED CODE ###

N, M=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(M)]
b=set()
for i,j in ab:
    if i==1 or j==N:
        b.add((i,j))
print("IM"*(not(any(((1,i) in b and (i,N) in b) for i in range(N))))+"POSSIBLE")
### BUGGY CODE ###

x,n = map(int,input().split())
p = list(map(int,input().split()))
i = 0
if n == 0:
    print(x)
else:
    while True:
        if not x - i in p:
            print(x-i)
            break
        elif not x + i in p:
            print(x+i)
        else:
            i += 1

### FIXED CODE ###

x,n = map(int,input().split())
p = list(map(int,input().split()))
i = 0
if n == 0:
    print(x)
else:
    for i in range(101):
        if not x - i in p:
            print(x-i)
            break
        elif not x + i in p:
            print(x+i)
            break
        else:
            i += 1
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    n,m = map(int,input().split())
    edge = [[] for _ in [0]*n]
    for _ in range(m):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)


    new = [[i] for i in range(n)]
    res = []
    tank = []
    res2 = -1

    while len(new) > 0:
        tank = []
        for i in range(len(new)):
            el = new[i]

            for go in edge[el[-1]]:
                if not go in el:
                    if el[0] in edge[go]:
                        print(len(el)+1)
                        for e in el:
                            print(e+1)
                        print(go+1)

                        exit()
                    tank.append(el+[go])
        new = tank
        
    print(-1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

n,m = map(int,input().split())

edge = [[] for _ in [0]*n]
back = [[] for _ in [0]*n]

for _ in [0]*m:
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    back[b-1].append(a-1)


res = [None]*(n+1)

for end in range(n):
    for start in edge[end]:
        cost = [-1]*n
        cost[start] = 0
        new = [start]
        tank = []
        judge = True

        while len(new) > 0 and judge:
            tank = []
            for fr in new:
                for go in edge[fr]:
                    if cost[go] < 0:
                        cost[go] = cost[fr] + 1
                        tank.append(go)
                        if go == end:
                            judge = False
            new = tank

        
        if cost[end] >= 0 and cost[end] < len(res):
            p = end
            res = [p+1]
            while p != start:
                for e in back[p]:
                    if cost[p] == cost[e]+1:
                        p = e
                        res.append(p+1)
                        break
if res[0] == None:
    print(-1)
else:                      
    print(len(res))
    for e in res:
        print(e)
### BUGGY CODE ###

a, b = map(int, input().split())
slist = []
if (a >= b):
    for i in range(1,b+1):
        if (a%i == 0 and b%i == 0):
            slist.append(i)
elif(a < b):
    for i in range(1, a):
        if (a%i == 0 and b%i == 0):
            slist.append(i)
print(slist[-1])
        
            


### FIXED CODE ###

a, b = map(int, input().split())
slist = []
if (a > b):
    c = a%b
    d = b
    while (c != 0 and d != 0):
        if (c < d):
            d = d%c
        elif (c > d):
            c = c%d
    if(c == 0):
        print(d)
    elif(d == 0):
        print(c)
        
    
elif(a < b):
    c = a
    d = b%a
    while (c != 0 and d != 0):
        if (c < d):
             d = d%c
        elif (c > d):
            c = c%d
    if(c == 0):
        print(d)
    elif(d == 0):
        print(c)
        
else:
    print(a)
### BUGGY CODE ###

import math

def cal(N):
    num=math.ceil(N**0.5)
    num=int(num)
    for i in range(num,N+1):
       if N%i==0:
           x=str(i)
           break
    return x

x=cal(int(input()))
print(len(x))

### FIXED CODE ###

def cal(N):
    num=(N**0.5)//1
    num=int(num)
    for i in range(num,0,-1):
       if N%i==0:
           k=int(N/i)
           x=len(str(k))
           break
    return x

print(cal(int(input())))
### BUGGY CODE ###

#!/usr/bin/env python3

N = int(input())
H = list(map(int, input().split()))
L = [None]*N
R = [None]*N

for i in range(N):
    L[i] = i+1 + H[i]
    R[i] = i+1 - H[i]

cnt = 0

for i in range(N):
    for j in range(N):
        if i < j:
            if L[i] == R[j]:
                cnt += 1

print(cnt)

### FIXED CODE ###

#!/usr/bin/env python3

from collections import Counter

N = int(input())
H = list(map(int, input().split()))
L = []
R = []

for i, j in enumerate(H):
    L.append(i+j)
    R.append(i-j)

b = Counter(R)
ans = 0

for i in L:
    ans += b.get(i,0)
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
now = 1
for _ in range(Q):
    query = [i for i in input().split()]
    if(query[0] == '2'):
        if(query[1]=='1'):
            if(now == 1):
                S = query[2] + S
            else:
                S += query[2]
        else:
            if(now == 1):
                S += query[2]
            else:
                S = query[2] + S
    else:
        now *= -1

print(S[::now])

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    S = input()[:-1]
    Q = int(input())
    li = [[] for _ in range(2)]
    now = 0
    for _ in range(Q):
        x = input()
        if(x[0] == '2'):
            if(x[2]=='1'):
                li[1-now].append(x[4])
            else:
                li[now].append(x[4])
        else:
            now = 1-now

    s = ''.join(li[1-now][::-1]) + S[::-(now*2-1)] + ''.join(li[now])
    print(s)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

h, w = map(int, input().split())
S = [0 for i in range(h)]
P = []

for i in range(h):
    S[i] = input()
    for j in range(len(S[i])):
        if S[i][j] == '.':
            P.append([i, j])
        else:
            pass

MV = [[-1, 0], [1, 0], [0, -1], [0, 1]]   #Move Vectol
ans = 0
def print_field(L:list):
    for i in range(len(L)):
        print(L[i])
    
def try_move(ch:int, cw:int, M:list):
    if 0 <= ch and ch < h and 0 <= cw and cw < w:
        if M[ch][cw] == '.':
            return True
        else:
            pass
    else:
        pass
    return False

def search_root(ch:int, cw:int, time:int, M:list):
    global md
    #print('time = ', time)
    if ch == gh and cw == gw:
        #print('gtime = ',time)
        if time < md:
            md = time
        else:
            pass
    else:
        for i in range(4):
            if try_move(ch+MV[i][0], cw+MV[i][1], M) == True:
                R = M[:]
                R[ch+MV[i][0]] = R[ch+MV[i][0]][0:cw+MV[i][1]] + '〇' + R[ch+MV[i][0]][cw+MV[i][1]+1:]
                #print_field(R)
                search_root(ch+MV[i][0], cw+MV[i][1], time+1, R)
            else:
                pass

ans = 0
for i in range(len(P)):
    for j in range(i+1, len(P)):
        md = h*w
        F = S[:]
        sh, sw = P[i]
        gh, gw = P[j]
        search_root(sh, sw, 0, F)
        if ans < md:
            ans = md
        else:
            pass
print(ans)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
S = [0 for i in range(h)]
for i in range(h):
    S[i] = input()

Di = [-1, 1, 0, 0] #Direction i
Dj = [0, 0, -1, 1] #Direction j
inf = 1000

def update_data(i:int, j:int, x:int):
    if Dist[i][j] == inf:
        Dist[i][j] = x
        Q.append([i, j])
    else:
        pass

ans = 0
for si in range(h):
    for sj in range(w):
        Dist = [[inf for j in range(w)] for i in range(h)]   #Distance
        if S[si][sj] == '.':
            Q = deque([])
            update_data(si, sj, 0)
            #BFS
            while len(Q) != 0:
                i, j  = Q[0][0], Q[0][1]
                Q.popleft()
                for dr in range(4):
                    ni , nj = i+Di[dr], j+Dj[dr]
                    if 0 <= ni and ni < h and 0 <= nj and nj < w:
                        if S[ni][nj] == '.':
                            update_data(ni, nj, Dist[i][j]+1)
                        else:
                            pass
                    else:
                        pass
            for i in range(h):
                for j in range(w):
                    if Dist[i][j] == inf:
                        pass
                    else:    
                        if ans < Dist[i][j]:
                            ans = Dist[i][j]
                        else:
                            pass
        else:
            pass
print(ans)
### BUGGY CODE ###

import sys
from heapq import heappush, heappop
n = int(input())
a = [int(e) for e in input().split()]
b = [int(e) for e in input().split()]
result = 0
finished = 0
for i in range(n):
  if a[i] == b[i]:
    finished += 1
hq = []
for i in range(n):
  if a[i] == b[i]:
    continue
  heappush(hq, (-b[i], i))
while True:
  _, i = heappop(hq)
  if i == 0:
    b[i] -= b[n - 1] + b[1]
  elif i == n -1:
    b[i] -= b[n - 2] + b[0]
  else:
    b[i] -= b[i - 1] + b[i + 1]
  if a[i] > b[i]:
    print(-1)
    sys.exit()
  result += 1
  if a[i] == b[i]:
    finished += 1
    if finished == n:
      print(result)
      sys.exit()
  else:
    heappush(hq, (-b[i], i))


### FIXED CODE ###

def main():
  import sys
  _int = int
  n = _int(input())
  a = [_int(e) for e in input().split()]
  b = [_int(e) for e in input().split()]
  result = 0
  q = [i for i in range(n) if b[i] != a[i]]
  while len(q) != 0:
    nq = []
    c = 0
    for i in q:
      if i == 0 or i == n - 1:
        j = b[(n + i - 1) % n] + b[(n + i + 1) % n]
      else:
        j = b[i - 1] + b[i + 1]
      if j > b[i] - a[i]:
        nq.append(i)
        continue
      c += 1
      k = (b[i] - a[i]) // j
      result += k
      b[i] -= j * k
      if a[i] != b[i]:
        nq.append(i)
    if c == 0 and len(nq) != 0:
      print(-1)
      sys.exit()
    q = nq
  print(result)
main()
### BUGGY CODE ###

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

pos = 0
saidai = 0
for i in range(N-K+1):
  temp = sum(p[i:i+K])
  if saidai < temp:
    saidai = temp
    pos = i
    
kitaichi = 0
for i in range(K):
  temp = sum(list(range(p[pos+i] + 1)))
  kitaichi = kitaichi + float(temp/p[pos+i])
  
print('{:.12f}'.format(kitaichi))

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
 
now = sum(p[:K])
saidai = now
for i in range(K, N):
  now -= p[i-K]
  now += p[i]
  if now > saidai:
    saidai = now
 
print('{:.12f}'.format((saidai + K)/2))
### BUGGY CODE ###

import itertools
from collections import defaultdict
H,W,N=map(int, raw_input().split())

d=[-1,0,1]
D=list(itertools.product(d,d))

C=set()	#Center
A=defaultdict(lambda: 0)
for i in range(N):
	a,b=map(int, raw_input().split())
	A[(a,b)]=1
	for dx,dy in D:
		cx=a+dx
		cy=b+dy
		if cx>=2 and cx<=H-1 and cy>=2 and cy<=W-1:
			C.add( (cx,cy) )

l=defaultdict(lambda: 0)

for x,y in C:
	cnt=0
	for i,j in D:
		if A[(x+i,y+j)]==1:
			cnt+=1
	l[cnt]+=1



for i in range(10):
	if i==0:
		print (H-2)*(W-2)-sum(l.values())
	else:
		print l[i]




### FIXED CODE ###

import itertools
from collections import defaultdict
from collections import Counter
H,W,N=map(int, raw_input().split())

d=[-1,0,1]
D=list(itertools.product(d,d))

A=defaultdict(lambda: 0)
for i in range(N):
	a,b=map(int, raw_input().split())
	for dx,dy in D:
		cx=a+dx
		cy=b+dy
		if cx>=2 and cx<=H-1 and cy>=2 and cy<=W-1:
			A[(cx,cy)]+=1

C=Counter(A.values())


for i in range(10):
	if i==0:
		print (H-2)*(W-2)-sum(C.values())
	else:
		print C[i]
### BUGGY CODE ###

temp = input().split(" ")
N = int(temp[0])
M = int(temp[1])
H = input().split(" ")
good = list(range(N))
for i in range(M):
    root = input().split(" ")
    a = int(root[0])-1
    b = int(root[1])-1
    if H[a]>H[b]:
        good = [i for i in good if i!=b]
    elif H[a]<H[b]:
        good = [i for i in good if i!=a]
    else:
        good = [i for i in good if i!=a and i!=b]
print(len(good))

### FIXED CODE ###

temp = input().split(" ")
N = int(temp[0])
M = int(temp[1])
H = input().split(" ")
good = [1] * N
for i in range(M):
    root = input().split(" ")
    a = int(root[0])-1
    b = int(root[1])-1
    if int(H[a])>=int(H[b]):
        good[b] = 0
    if int(H[a])<=int(H[b]):
        good[a] = 0
print(sum(good))
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

h, w = MAP()
A = [list(input()) for i in range(h)]

def bfs():
    que = deque([])
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    d = [[INF] * w for i in range(h)]
     
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                sy, sx = i, j
                d[sy][sx] = 0
                que.append((sy, sx))
    ans = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny, nx = p[0] + dy[i], p[1] + dx[i]
            
            if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == INF and A[ny][nx] == ".":
                d[ny][nx] = d[p[0]][p[1]] + 1
                A[ny][nx] = "#"
                que.append((ny, nx))
                ans = max(ans, d[ny][nx])     
    
    return ans



print(bfs())

    


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

h, w = MAP()
A = [list(input()) for i in range(h)]


def bfs():
    que = deque([])
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    d = [[INF] * w for i in range(h)]
    
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                sy, sx = i, j
                d[sy][sx] = 0
                que.append((sy, sx))
    ans = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny, nx = p[0] + dy[i], p[1] + dx[i]
            
            if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == INF and A[ny][nx] == ".":
                d[ny][nx] = d[p[0]][p[1]] + 1
                # A[ny][nx] = "#"
                que.append((ny, nx))
 
                ans = max(ans, d[ny][nx])     
#    print(*d, sep="\n")
    return ans


if __name__ == "__main__":
    print(bfs())
### BUGGY CODE ###

n = int(input())

c, s, f = [], [], []
for _ in range(n-1):
    x,y,z = map(int,input().split())
    c.append(x)
    s.append(y)
    f.append(z)

for i in range(n-1):
    tmp = 0
    for j in range(i, n-1):
        for k in range(10**8):
            if tmp <= s[j] + f[j] * k:
                tmp = s[j] + f[j] * k + c[j]
                break
    else:
        print(tmp)

print(0)

### FIXED CODE ###

n = int(input())

c, s, f = [], [], []
for _ in range(n-1):
    x,y,z = map(int,input().split())
    c.append(x)
    s.append(y)
    f.append(z)

anss =[]
for i in range(n-1):
    tmp = 0
    for j in range(i, n-1):
        k = 0
        while 1:
            if tmp <= s[j] + f[j] * k:
                tmp = s[j] + f[j] * k + c[j]
                break
            else:
                k += 1
    else:
        anss.append(tmp)
else:
    anss += [0]

for ans in anss:
    print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
P=[i-1 for i in P]
C=list(map(int,input().split()))
import math
ans=-10**18
for i in range(N):
  x=i
  tot=0
  cycle=[]
  while True:
    x=P[x]
    cycle.append(C[x])
    tot+=C[x]
    if x==i:
      break
  L=len(cycle)
  t=0
  for i in range(L):
    t+=cycle[i]
    if i+1>K:
      break
    now=t
    if tot>0:
      e=(K-i-1)//L
      now+=tot*e
    ans=max(ans,now)

print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
P=[i-1 for i in P]
C=list(map(int,input().split()))
import math
ans=-10**18
for i in range(N):
  x=i
  tot=0
  cycle=[]
  while True:
    x=P[x]
    cycle.append(C[x])
    tot+=C[x]
    if x==i:
      break
  L=len(cycle)
  t=0
  for i in range(L):
    t+=cycle[i]
    if i+1>K:
      break
    now=t
    if tot>0:
      e=(K-i-1)//L
      now+=tot*e
    ans=max(ans,now)

print(ans)