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

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    ans = -1
    que = collections.deque(e[s])
    cnt = 0
    finflg = True
    while len(que) and cnt < 10 ** 6 and finflg:
        cnt += 1
        finflg = True

        for _ in range(3):
            for i in range(len(que)):
                nxt = que.popleft()
                if _ == 2 and nxt == t:
                    ans = cnt
                    finflg = False
                for tmp in e[nxt]:
                    que.append(tmp)

    print(-1 if ans == -1 else ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    visited = [[True] * 3 for _ in range(n)]

    que = collections.deque()
    que.append([0, s])
    visited[s][0] = False
    cnt = 0
    ans = -1
    flg = True

    while que and flg:
        cnt += 1
        for _ in range(len(que)):
            i, q = que.popleft()
            for ei in e[q]:
                tmp = (i + 1) % 3
                if tmp == 0 and ei == t:
                    ans = cnt // 3
                    flg = False
                    break
                elif visited[ei][tmp]:
                    visited[ei][tmp] = False
                    que.append([tmp, ei])

    print(ans)


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

def maxim(i,char):
    if i<0:
        return 0
    if d[i,char]!=-1:
        return d[i,char]
    if char=='C':
        d[i,char]= max(c[i]+maxim(i-1,'B'),c[i]+maxim(i-1,'A'))
        return d[i,char]
    if char=='B':
        d[i,char]= max(b[i] + maxim(i - 1, 'A'), b[i] + maxim(i - 1, 'C'))
        return d[i,char]
    if char=='A':
        d[i,char]= max(a[i] + maxim(i - 1, 'B'), a[i] + maxim(i - 1, 'C'))
        return d[i,char]
n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=map(int,input().split())
    d=dict()
    for i in range(n):
        d[i,'A']=-1
        d[i,'B']=-1
        d[i,'C']=-1


    a.append(x)
    b.append(y)
    c.append(z)
print(max(maxim(n-1,'C'),maxim(n-1,'B'),maxim(n-1,'A')))




### FIXED CODE ###

import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()


n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=get_ints()
    
    a.append(x)
    b.append(y)
    c.append(z)
li=[[-1 for i in range(3)]for j in range(n)]
li[0][0],li[0][1],li[0][2]=a[0],b[0],c[0]
for i in range(1,n):


        li[i][0] = max(a[i] + li[i-1][1] ,a[i] + li[i - 1][2])

        li[i][1] = max(b[i] + li[i - 1][0], b[i] +li[i - 1][2])

        li[i][2] = max(c[i] + li[i - 1][1], c[i] + li[i - 1][0])
print(max(li[n-1]))
### BUGGY CODE ###

L,R = map(int,input().split())
S = set()
T = set()
if (R-L)>=673:
    print(0)
else:
    l = L%2019
    for i in range(R-L+1):
        S = S | {l+i}
    for i in S:
        for j in S:
            if i != j:
                T = T | {(i*j)%2019}
    print(min(T))

### FIXED CODE ###

L,R = map(int,input().split())
S = list()
n = R-L
if n >= 673:
    print(0)
else:
    for i in range(n+1):
        for j in range(i+1,n+1):
            l = L+i
            r = L+j
            S.append((l*r)%2019)
    print(min(S))
### BUGGY CODE ###

n = int(input())

sum = 0

for i in range(n):
    sum += i
    
print(sum)

### FIXED CODE ###

n = int(input())
    
print(int((n*(n-1))//2))
### BUGGY CODE ###

X, Y, A, B, C = map(int ,input().split(' '))
p = list(map(int ,input().split(' ')))
q = list(map(int ,input().split(' ')))
R = list(map(int ,input().split(' ')))

eat = sorted(p, reverse=True)[:X]
eat[len(eat):] = sorted(q, reverse=True)[:Y]

for r in R:
  if r>min(eat):
    eat.remove(min(eat))
    eat.append(r)
  
print(sum(eat))


### FIXED CODE ###

X, Y, A, B, C = map(int ,input().split(' '))
p = list(map(int ,input().split(' ')))
q = list(map(int ,input().split(' ')))
R = list(map(int ,input().split(' ')))
 
eat = sorted(p, reverse=True)[:X]
eat[len(eat):] = sorted(q, reverse=True)[:Y]
eat[len(eat):] = R
eat.sort(reverse=True)


print(sum(eat[:X+Y]))
### BUGGY CODE ###

N,K = map(int,input().split())
while True:
  if abs(N)>abs(N-K):
    N-=K
  else:
    print(abs(N))
    exit()

### FIXED CODE ###

n, k = map(int, input().split())
ans1 = n%k
ans2 = -(ans1-k)

print(min(ans1, ans2))
### BUGGY CODE ###

def main():    
    t =  int(input())
    n = 1
    a = list(map(int,input().strip().split()))[:t]
    for i in range(t):
        n*=a[i]
    if n>1e18:
        print(-1)
    else:
        print(n)
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():    
    t =  int(input())
    n = 1
    a = list(map(int,input().strip().split()))[:t]
    for i in range(t):
        if a[i]==0:
            return 0
    for i in range(t):
        n*=a[i]
        if n>1e18:
            return -1
    if n>1e18:
        return -1
    else:
        return n
        
if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

import sys
from math import sqrt
n = int(input())
a = [int(input()) for _ in range(n+1)]
#xx = [0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5, 6, -6]
x = 0
#for x in xx:
while True:
	m = abs(sum([a[i]*pow(x, n-i) for i in range(n+1)]))
	if m != 0:
		break
	x += 1
ps = []

i = 2
while i**2 <= m:
#for i in range(2, int(sqrt(m))+1):
	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
	i += 1
if m != 1:
	ps.append(m)
if n == 0:
	if ps:
		print(*ps, sep="\n")
	sys.exit()
a = a[::-1]
for p in ps:
	if p-1 > n:
		ng = False
		for i in range(1, n+1):
			if a[i]%p != 0:
				ng = True
				break
		if not ng:
			print(p)
	else:
		mods = [0 for _ in range(p-1)]
		for i in range(1, n+1):
			mods[i%(p-1)] += a[i]
			mods[i%(p-1)] %= p
		if mods[0] == 0:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 0:
					ng = True
					break
			if not ng:
				print(p)

### FIXED CODE ###

import sys
from fractions import gcd
n = int(input())
a = [int(input()) for _ in range(n+1)]
x = 0
while True:
	m = abs(sum([a[i]*pow(x, n-i) for i in range(n+1)]))
	if m != 0:
		break
	x += 1
ps = []

i = 2
while i**2 <= m and i <= n+1:
#for i in range(2, int(sqrt(m))+1):
	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
	i += 1
if m != 1 and n != 0:
	ps.append(m)
#print(ps)
g = a[0]
for i in range(1, n+1):
	g = gcd(g, abs(a[i]))

#print(g)
ans = []

i = 2
while i**2 <= g:
#for i in range(2, int(sqrt(m))+1):
	if g%i == 0:
		if i >= n+1:
			ans.append(i)
		while g%i == 0:
			g //= i
	i += 1
if g != 1 and g >= n+1:
	ans.append(g)

a = a[::-1]
for p in ps:
	if p-1 > n:
		ng = False
		for i in range(1, n+1):
			if a[i]%p != 0:
				ng = True
				break
		if not ng:
			ans.append(p)
	else:
		mods = [0 for _ in range(p-1)]
		for i in range(1, n+1):
			mods[i%(p-1)] += a[i]
			mods[i%(p-1)] %= p
		if mods[0] == 0:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 0:
					ng = True
					break
			if not ng:
				ans.append(p)
ans = sorted(list(set(ans)))
if ans:
	print(*ans, sep="\n")
### BUGGY CODE ###

K = int(input())

if(K%2 == 0):
    print("-1")
    exit()

A = 7
ans = 1
while(A < K):
    A = A*10 + 7
    ans += 1

while(True):
    #print(A)
    A = A % K
    if(A==0):
        print(ans)
        exit()
    A = A * 10 + 7
    ans += 1


### FIXED CODE ###

K = int(input())

if(K%2 == 0):
    print("-1")
    exit()

A = 7
ans = 1
while(A < K): #O(6)
    A = A*10 + 7
    ans += 1

while(True):
    #print(A)
    A = A % K #1
    if(ans > K):
        print("-1")
        exit()
    if(A==0): #1
        print(ans)
        exit()
    A = A * 10 + 7 # 1
    ans += 1# 1
### BUGGY CODE ###

X,K,D=map(int,input().split())
if X==D:
    if K%2==0:
        print(D)
    else:
        print(0)
else:
    for i in range(K):
        if abs(X+D)>abs(X-D):
            X=X-D
        else:
            X=X+D
    print(abs(X))

### FIXED CODE ###

X,K,D=map(int,input().split())
if X>=0:
    if K<int(X/D):
        print(abs(X-K*D))
    else:
        if abs(X-(int(X/D)+1)*D)<abs(X-int(X/D)*D):
            A=X-(int(X/D)+1)*D
            if (K-(int(X/D)+1))%2==0:
                print(abs(A))
            else:
                if abs(A+D)<abs(A-D):
                    print(abs(A+D))
                else:
                    print(abs(A-D))
        else:
            A=X-(int(X/D))*D
            if (K-(int(X/D)))%2==0:
                print(abs(A))
            else:
                if abs(A+D)<abs(A-D):
                    print(abs(A+D))
                else:
                    print(abs(A-D))
else:
    if K<int(abs(X)/D):
        print(abs(X+K*D))
    else:
        if abs(X+(int(abs(X)/D)+1)*D)<abs(X+int(abs(X)/D)*D):
            A=X+(int(abs(X)/D)+1)*D
            if (K-(int(abs(X)/D)+1))%2==0:
                print(abs(A))
            else:
                if abs(A+D)<abs(A-D):
                    print(abs(A+D))
                else:
                    print(abs(A-D))
        else:
            A=X+(int(abs(X)/D))*D
            if (K-(int(abs(X)/D)))%2==0:
                print(abs(A))
            else:
                if abs(A+D)<abs(A-D):
                    print(abs(A+D))
                else:
                    print(abs(A-D))
### BUGGY CODE ###

n,k = map(int,input().split())
tele = {}
a = list(map(int,input().split()))
for i in range(1,n+1):
    tele[i] = a[i-1]
lis=[1]
now = 1
n = 1
while tele[now] not in lis:
    lis.append(tele[now])
    now = tele[now]
p = lis.index(tele[now])
q = len(lis) - p
if k <= p:
    print(lis[k])
else:
    print(lis[(k-p)%q + p])

### FIXED CODE ###

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

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

l=[1]
di={}
di[1]=1

for i in a:
    b=a[l[-1]-1]
    if b in di:
        x=b
        break
    l.append(b)
    di[b]=1
t1=0
for j in l:
    if j==x:
        break
    else:
        t1+=1

t2=len(l)-t1
if k<=t1:
    print(l[k])

else:
    aa=(k-t1)%t2
    print(l[t1+aa])
### BUGGY CODE ###

import math
import itertools

N=int(input())

GCD=[]
GCD1=[]
for i in range (1,N+1):
	GCD.append(i)
 
for i in itertools.product(GCD,repeat=3):
   
	GCD1.append(math.gcd(math.gcd(i[0],i[1]),i[2]))
 
print(sum(GCD1))

### FIXED CODE ###

import math
import itertools
GCD_over_150=[4548003,4616104,4718640,4812789,4918561,5003286,5131848,5205481,5299011,5392008,5521384,5610705,5739009,5818390,5930196,6052893,6156139,6239472,6402720,6493681,6623853,6741078,6864016,6953457,7094451,7215016,7359936,7475145,7593865,7689630,7886244,7984165,8130747,8253888,8403448,8523897,8684853,8802826,8949612,9105537,9267595,9376656,9574704,9686065,9827097,9997134,10174780,10290813,10493367,10611772,10813692]
 
N=int(input())
if N<150:
	GCD=[]
	GCD1=[]
	for i in range (1,N+1):
		GCD.append(i)
	for i in itertools.product(GCD,repeat=3):
		GCD1.append(math.gcd(math.gcd(i[0],i[1]),i[2]))
	print(sum(GCD1))    
else:
    print(GCD_over_150[N-150])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, Z, W = list(map(int, input().split()))
A = [W] + list(map(int, input().split()))

S = set(A)
GX = {s:[None]*N + [abs(A[N]-s)] for s in S}
GY = {s:[None]*N + [abs(A[N]-s)] for s in S}
minGX = {s:10**10 for s in S}
maxGY = {s:0      for s in S}

for k in range(N-1, -1, -1):
    ak = A[k]
    gx = max(GY[ak][k+1], maxGY[ak])
    gy = min(GX[ak][k+1], minGX[ak])
    for s in S:
        GX[s][k] = gx
        GY[s][k] = gy

    for s in S:
        maxGY[s] = max(GY[s][k+1], maxGY[s])
        minGX[s] = min(GX[s][k+1], minGX[s])

print(GX[W][0])

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, Z, W = list(map(int, input().split()))
A = [W] + list(map(int, input().split())) # A[0]=W, A[i]=ai

GX = [None]*N # GX[i] := YがA[i] を取った直後の状況から到達しうる最大のスコア
GY = [None]*N # GY[i] := XがA[i] を取った直後の状況から到達しうる最小のスコア
minGX = 10**20
maxGY = 0

for k in range(N-1, -1, -1):
    GX[k] = max(abs(A[k]-A[N]), maxGY)
    GY[k] = min(abs(A[k]-A[N]), minGX)
    minGX = min(minGX, GX[k])
    maxGY = max(maxGY, GY[k])

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

from collections import deque
n , m , k = map(int,input().split())
tomo = [set() for i in range(n+1)]
bro = [set() for i in range(n+1)]
for i in range(m):
    a , b = map(int,input().split())
    tomo[a].add(b)
    tomo[b].add(a)
for i in range(k):
    c , d = map(int,input().split())
    bro[c].add(d)
    bro[d].add(c)

visit = [True for i in range(n+1)]
kurasuta = []
for i in range(1,n+1):
    if visit[i]:
        kar = {i}
        d = deque()
        d.append(i)
        visit[i] = False
        while d:
            now = d.popleft()
            for j in tomo[now]:
                if visit[j]:
                    visit[j] = False
                    kar.add(j)
                    d.append(j)
        kurasuta.append(kar)
    else:
        continue
ans = [0 for i in range(n)]

for i in range(len(kurasuta)):
    for j in kurasuta[i]:
        ans[j-1] = len(kurasuta[i] - tomo[j] - bro[j]) - 1

print(*ans)

### FIXED CODE ###

from collections import deque
n , m , k = map(int,input().split())
tomo = [set() for i in range(n+1)]
to = [0 for i in range(n+1)]
bro = [set() for i in range(n+1)]
for i in range(m):
    a , b = map(int,input().split())
    tomo[a].add(b)
    tomo[b].add(a)
    to[a] += 1
    to[b] += 1
for i in range(k):
    c , d = map(int,input().split())
    bro[c].add(d)
    bro[d].add(c)

visit = [True for i in range(n+1)]
kurasuta = []
for i in range(1,n+1):
    if visit[i]:
        kar = {i}
        d = deque()
        d.append(i)
        cou = 1
        visit[i] = False
        while d:
            now = d.popleft()
            for j in tomo[now]:
                if visit[j]:
                    visit[j] = False
                    kar.add(j)
                    d.append(j)
                    cou += 1
        kurasuta.append([kar,cou])
    else:
        continue
ans = [0 for i in range(n)]

for i in range(len(kurasuta)):
    for j in kurasuta[i][0]:
        ans[j-1] = kurasuta[i][1] - to[j] - 1 - len(kurasuta[i][0] & bro[j])

print(*ans)
### BUGGY CODE ###

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a = [0]
b = [0]
for i in range(n):
  a.append(a[i]+A[i])
for j in range(m):
  b.append(b[j]+B[j])
#print(a,b)

ans = 0
for i in range(n+1):
  j = 0
  if a[i] > k:
    break
  while (k - a[i]) >= b[j]:
    j += 1
    if j == m:
      break
  
  if k < (a[i] + b[j]):
      j -= 1
  ans = max(ans, i+j)
     
print(ans)


### FIXED CODE ###

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
 
a = [0]
b = [0]
for i in range(n):
  a.append(a[i]+A[i])
for j in range(m):
  b.append(b[j]+B[j])
#print(a,b)
 
ans = 0
j = m
for i in range(n+1):
  if a[i] > k:
    break
  while (k - a[i]) < b[j]:
    j -= 1
    if j == -1:
      break
  
  ans = max(ans, i+j)
     
print(ans)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : map(int, stdin.readline().split())

def main():
  n = ni()
  a = list(na())
  res = []
  for i in range(1,n+1):
    res.append(a.index(i)+1)
  print(*res)

main()

### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : map(int, stdin.readline().split())

def main():
  n = ni()
  a = list(na())
  d = {}
  for i, a in enumerate(a):
    d[a] = i+1
  res = []
  for i in range(n):
    res.append(d[i+1])
  print(*res)

main()
### BUGGY CODE ###

class Doubling:
    m = 0
    to = [[]]
    # fを次の値を得る関数として、[0,n)のvについて最大でf^k(v)を得られる。
    def __init__(self, n, f, k):
        while k > 0:
            k = k >> 1
            self.m += 1
        self.to = [[-1] * n for _ in range(self.m+1)]
        for j in range(n):
            self.to[0][j] = f(j)
        for i in range(self.m):
            for j in range(n):
                if self.to[i][j] == -1:
                    self.to[i+1][j] = -1
                else:
                    self.to[i+1][j] = self.to[i][self.to[i][j]]

    # p番目の値のq個先を得る。
    def query(self, p, q):
        for i in range(self.m+1):
            if p == -1:
                break
            if (q >> i) & 1:
                p = self.to[i][p]
        return p

n,k = map(int, input().split())
a = list(map(int, input().split()))

d = Doubling(n, lambda x: a[x]-1, k)
print(d.query(0, k) + 1)


### FIXED CODE ###

class Doubling:
    m = 0
    to = [[]]
    # fを次の値を得る関数として、[0,n)のvについて最大でf^k(v)を得られる。
    def __init__(self, n, f, k):
        while k > 0:
            k = k >> 1
            self.m += 1
        self.to = [[-1] * n for _ in range(self.m+1)]
        for j in range(n):
            self.to[0][j] = f(j)
        for i in range(self.m):
            for j in range(n):
                if self.to[i][j] == -1:
                    self.to[i+1][j] = -1
                else:
                    self.to[i+1][j] = self.to[i][self.to[i][j]]

    # p番目の値のq個先を得る。
    def query(self, p, q):
        for i in range(self.m+1):
            if p == -1:
                break
            if (q >> i) & 1:
                p = self.to[i][p]
        return p

n,k = map(int, input().split())
a = list(map(int, input().split()))

d = Doubling(n, lambda x: a[x]-1, k)
print(d.query(0, k) + 1)
### BUGGY CODE ###

s=input()
flag=1
length=len(s)
while flag:
    l=len(s)
    if l<=1:
        break
    for i in range(1,l):
        if s[i-1]!=s[i]:
            s=s[:i-1]+s[i+1:]
            break
        elif i==l-1:
            flag=0
print(length-len(s))

### FIXED CODE ###


s=input()
length=len(s)
cnt=[0,0]
for i in range(length):
    if s[i]=='0':
        cnt[0]+=1
    else:
        cnt[1]+=1
print(min(cnt)*2)
### BUGGY CODE ###

from collections import deque
def main():
    H, W = map(int,input().split())
    s = [list(map(str,input())) for _ in range(H)]
    dist = [[-1]*W for _ in range(H)]
    
    q = deque([])
    for i in range(H):
        for j in range(W):
            if s[i][j] == "#":
                dist[i][j] = 0
                q.append((i, j))
    
    ans = 0
    while q:
        x, y = q.popleft()
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if (0 <= nx < H and 0 <= ny < W and dist[nx][ny] == -1 and s[nx][ny] == '.'):
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
                ans = max(ans, dist[nx][ny])
                
    print(ans)

if __name__ == "__main__":
    main()
                

### FIXED CODE ###

import numpy
H,W = map(int,input().split())
a_list = []
INF = 10**10
for i in range(H):
    str = input()
    a_list.append([0 if i == "#" else INF for i in list(str)])

a_list = numpy.array(a_list)
for x in range(W-1):
    a_list[:,x+1] = numpy.minimum(a_list[:,x]+1,a_list[:,x+1])
    a_list[:,-x-2] = numpy.minimum(a_list[:,-x-1]+1,a_list[:,-x-2])

for y in range(H-1):
    a_list[y+1,:] = numpy.minimum(a_list[y,:]+1,a_list[y+1,:])
    a_list[-y-2,:] = numpy.minimum(a_list[-y-1,:]+1,a_list[-y-2,:])

print(a_list.max())
### BUGGY CODE ###

s = str(input())
ans = 0 

for st in ['01', '10']:
    while st in s:
        for i in range(len(s)):
            if s[i:i+2] == st:
                s = s[:i] + s[i+2:]
                ans += 2

print(ans)


### FIXED CODE ###

s = str(input())
z = sum([str(x)=='0' for x in s])
o = sum([str(x)=='1' for x in s])
print(2*min(z, o))
### BUGGY CODE ###

I0 = lambda :map(int,input().split())
I1 = lambda :int(input())
I2 = lambda :list(map(int,input().split()))
#####################################################


from sys import stdin,setrecursionlimit
setrecursionlimit(10**6)
def dfs(p,father=-1):
    for i in tree[p]:
        if i == father:
            continue
        counter[i]+=counter[p]
        dfs(i,p)

n ,q = I0()
counter = [0]*n
tree = [[] for i in range(n)]
for i in range(n-1):
    a,b=I0()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for i in range(q):
    p,x = I0()
    counter[p-1]+=x
dfs(0) 
print(*counter)



### FIXED CODE ###

I0 = lambda :map(int,input().split())
I1 = lambda :int(input())
I2 = lambda :list(map(int,input().split()))
#####################################################


from sys import stdin,setrecursionlimit
#from copy import deepcopy
 
setrecursionlimit(10**6)
input=stdin.readline

def dfs(p,father=-1):
    for i in tree[p]:
        if i == father:
            continue
        counter[i]+=counter[p]
        dfs(i,p)

n ,q = I0()
counter = [0]*n
tree = [[] for i in range(n)]
for i in range(n-1):
    a,b=I0()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for i in range(q):
    p,x = I0()
    counter[p-1]+=x
    

dfs(0)

print(*counter)

'''stack = [1]
while stack:
    yy = stack.pop()
    for i in tree[yy]:
        counter[i-1]+=counter[yy-1]
        stack.append(i)'''
### BUGGY CODE ###

n,k = map(int,input().split())
res_graph = [[1,i] for i in range(2,n+1)]
res = (n-1)*(n-2)//2

if(k > (n-2)*(n-1)//2):
    print(-1)
    exit()

tmp = 1
tmp_edge = 2

while 1:
    if res==k:
        break
    chek = [0]*(n-tmp_edge)
    for i in range(tmp_edge-1,len(chek)+1):
        res_graph.append([tmp_edge, i+tmp_edge])
        res -=1
        if(res==k):
            break
    tmp_edge+=1
    if res==k:
        break

print(len(res_graph))
for i,j in res_graph:
    print(i,j)


### FIXED CODE ###

n,k = map(int,input().split())
res_graph = [[1,i] for i in range(2,n+1)]
res = (n-1)*(n-2)//2

if(k > (n-2)*(n-1)//2):
    print(-1)
    exit()

tmp_edge = 2
while res!=k:
    tmp = 1
    for i in range(n-tmp_edge):
        res_graph.append([tmp_edge,tmp+tmp_edge])
        res-=1
        tmp+=1
        if res==k:
            break
    tmp_edge+=1

print(len(res_graph))
for i,j in res_graph:
    print(i,j)
### BUGGY CODE ###

def main():
    (n,k),p,c=[[*map(int,t.split())]for t in open(0)]
    m=-10**18
    for i in range(n):
        s=i
        t=1
        x=c[s]
        while p[s]-1!=i:
            s=p[s]-1
            t+=1
            x+=c[s]
        if x>0:
            a=(k//t-1)*x
            if a>m:m=a
            s=i
            for _ in range(k%t+t):
                s=p[s]-1
                a+=c[s]
                if a>m:m=a
        else:
            a=0
            s=i
            for _ in range(min(k,t)):
                s=p[s]-1
                a+=c[s]
                if a>m:m=a
    print(m)
main()

### FIXED CODE ###

def main():
    (n,k),p,c=[[*map(int,t.split())]for t in open(0)]
    m=-10**18
    for i in range(n):
        s=i
        t=1
        x=c[s]
        while p[s]-1!=i:
            s=p[s]-1
            t+=1
            x+=c[s]
        if x>0:
            a=(k//t-1)*x
            if a>m:m=a
            s=i
            for _ in range(k%t+t):
                s=p[s]-1
                a+=c[s]
                if a>m:m=a
        else:
            a=0
            s=i
            for _ in range(min(k,t)):
                s=p[s]-1
                a+=c[s]
                if a>m:m=a
    print(m)
main()