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

n = int(input())
l = []
for i in range(2,n):
    for j in range(2,n):
        l.append(i*j)
if n not in l:
    ans = n-1
else:
    lf = []
    for k in range(1, n+1):
        if n % k == 0:
            lf.append(k)
        i = lf[len(lf) // 2 - 1]
        j = lf[len(lf) // 2]
        ans = i + j - 2
print(ans)

### FIXED CODE ###

n = int(input())
ln = []
for k in range(1,(int(n**0.5))+1):
    if n % k == 0:
        ln.append(k)
if not n**0.5 % 1 == 0:
    for k in reversed(range(0, len(ln))):
        ln.append(n // ln[k])
else:
    for k in reversed(range(0, len(ln)-1)):
        ln.append(n // ln[k])
if not n**0.5 % 1 == 0:
    i = ln[len(ln) // 2 - 1]
    j = ln[len(ln) // 2]
    ans = i + j -2
else:
    ans = int(2*n**0.5)-2
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
s = str(input())

t = []
d = []

for _ in range(Q):
    ti, di = map(str, input().split())
    t.append(ti)
    d.append(di)
    
def is_dead(i):
    LEFT_DIE = -1
    RIGHT_DIE = len(s)
    for ti, di in zip(t, d):
        if s[i] == ti:
            if di == 'L':
                i -= 1
            if di == 'R':
                i += 1
            if i == LEFT_DIE or i == RIGHT_DIE:
                return True
    return False

def check_left():
    tmp = -1
    for i in range(len(s)):
        if is_dead(i):
            tmp = i
        else:
            return tmp

def check_right():
    tmp = len(s)
    for i in range(len(s)):
        i = len(s) - i - 1
        if is_dead(i):
            tmp = i
        else:
            return tmp
        
        

left_edge = check_left()
#print(left_edge)
right_edge = check_right()
#print(right_edge)

ans_s = s[left_edge+1:right_edge]
#print(ans_s)
ans = len(ans_s)
print(ans)

        
        
        
        
        
        

### FIXED CODE ###

N, Q = map(int, input().split())
s = str(input())

t = []
d = []

for _ in range(Q):
    ti, di = input().split()
    t.append(ti)
    d.append(di)
    
LEFT_DIE = -1
RIGHT_DIE = N

def is_dead(i):
    for ti, di in zip(t, d):
        if s[i] == ti:
            if di == 'L':
                i -= 1
            if di == 'R':
                i += 1
            if i == LEFT_DIE:
                return LEFT_DIE
            if i == RIGHT_DIE:
                return RIGHT_DIE
    return 0

low = -1
high = N;
# LEFT
while high - low > 1:
    mid = (low + high) // 2;
    if is_dead(mid) == LEFT_DIE:
        low = mid
    else:
        high = mid
left_edge = high

low = -1
high = N;
# RIGHT
while high - low > 1:
    mid = (low + high) // 2;
    if is_dead(mid) == RIGHT_DIE:
        high = mid
    else:
        low = mid
right_edge = low

#print(left_edge, right_edge)
ans_s = s[left_edge:right_edge+1]
#print(ans_s)
ans = len(ans_s)
print(ans)
### BUGGY CODE ###

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

ans=0
for i in range(n):
  p=a.pop()
  q=sum(a)
  ans+=p*q
print(ans%(10**9+7))

### FIXED CODE ###

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

s=sum(a)
ans=0
for i in range(n-1):
  s-=a[i]
  ans+=s*a[i]
print(ans%(10**9+7))
### BUGGY CODE ###

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

ans = 0
for i, A_i in enumerate(A):
    for A_j in (A[:i] + A[i+1:]):
        if (A_i / A_j) % 1 == 0:
            break
    else:
        ans += 1
print(ans)

### FIXED CODE ###

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

A.sort()
max_A = A[-1]
arr = [0] * (max_A + 1)

for val in A:
    arr[val] += 1
    if arr[val] == 1:
        for j in range(2*val, max_A + 1, val):
            arr[j] += 2

print(arr.count(1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
s = []
for _ in range(N):
    s.append(input())

#c = 0
out = 0
for c in range(N-1):
#while c < N-1:
    for i in range(c, N-1):
        s_l = set(s[c])
        s_r = set(s[i+1])
        if(s_l != s_r):
            continue
        s_l_li = list(s_l)
        for j in range(len(s_l_li)):
            if(s[c].count(s_l_li[j]) != s[i+1].count(s_l_li[j])):
                break
            if j == (len(s_l_li)-1):
                out += 1
#    c += 1
print(out)

### FIXED CODE ###

N = int(input())
D = {}
for _ in range(N):
    S = "".join(sorted(input()))
    if S in D:
        D[S] += 1
    else:
        D[S] = 1
 
out = 0
for i in D.values():
    out += i * (i-1) //2
print(out)
### BUGGY CODE ###

import numpy as np


def main():
    S = input()
    S = S[::-1]
    _T = 'dreamer', 'dream', 'eraser', 'erase'
    T = []
    for t in _T:
        T.append(t[::-1])
    while 1:
        temp = []
        for t in T:
            if S[:len(t)] == t:
                S = S[len(t):]
        for t in T:
            temp.append(t in S)
        if any(temp) == False:
            break
    if len(S) > 0:
        print('NO')
    else:
        print('YES')


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    S = input()
    S = S[::-1]
    _T = 'dreamer', 'dream', 'eraser', 'erase'
    T = []
    for t in _T:
        T.append(t[::-1])
    i = 0
    while 1:
        temp = []
        bool = True
        for t in T:
            if S[i:len(t) + i] == t:
                i += len(t)
                bool = False
        if bool:
            break
    if len(S) != i:
        print('NO')
    else:
        print('YES')


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

from collections import deque
n = int(input())
lst = [[set(),set()] for i in range(n)]
a = set([1])
b = set()
for i in range(n-1):
    u,v,w = map(int,input().split())
    if w % 2 == 0:
        lst[u-1][0].add(v)
        lst[v-1][0].add(u)
    else:
        lst[u-1][1].add(v)
        lst[v-1][1].add(u)
q = deque([1])
while q:
    i = q.popleft()
    if i in a:
        for j in lst[i-1][0]:
            lst[j-1][0].discard(i)
            q.append(j)
            a.add(j)
        for j in lst[i-1][1]:
            lst[j-1][1].discard(i)
            q.append(j)
            b.add(j)
    if i in b:
        for j in lst[i-1][0]:
            lst[j-1][1].discard(i)
            q.append(j)
            b.add(j)
        for j in lst[i-1][1]:
            lst[j-1][0].discard(i)
            q.append(j)
            a.add(j)
for i in range(1,n+1):
    if i in a:
        print(0)
    else:
        print(1)

### FIXED CODE ###

from collections import deque
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v,w = map(int,input().split())
    graph[u].append((v,w))
    graph[v].append((u,w))
q = deque([1])
ans = [0] * (n+1)
parent = [0]*(n+1)
while q:
    x = q.popleft()
    for y,w in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        ans[y] = ans[x]^(w&1)
        q.append(y)
for i in range(1,n+1):
    print(ans[i])
### BUGGY CODE ###

# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
# import sys ; sys.exit() # プログラム終了
# from copy import deepcopy ; b=deepcopy(a)
# chr(ord('a') + 1)
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#
from copy import deepcopy
from collections import deque

d = deque()
h, w = map(int, input().split())
s = [list(map(str, list(input()))) for i in range(h)]
used = [[True for j in range(w)] for i in range(h)]
# used = [[True]*w]*h
for i in range(h):
    for j in range(w):
        if (s[i][j] == "#"):
            d.append([i, j])

ans = -1
while (d):

    tmp = deque()
    while(d):
        i, j = d.popleft()
        used[i][j] = False

        if i+1 < h and used[i+1][j]:
            s[i+1][j] = "#"
            tmp.append([i+1, j])

        if i-1 >= 0 and used[i-1][j]:
            s[i-1][j] = "#"
            tmp.append([i-1, j])

        if j+1 < w and used[i][j+1]:
            s[i][j+1] = "#"
            tmp.append([i, j+1])

        if j-1 >= 0 and used[i][j-1]:
            s[i][j-1] = "#"
            tmp.append([i, j-1])

    d = tmp
    ans += 1

print(ans)


### FIXED CODE ###

# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
# import sys ; sys.exit() # プログラム終了
# from copy import deepcopy ; b=deepcopy(a)
# chr(ord('a') + 1)
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#
from copy import deepcopy
from collections import deque

d = deque()
h, w = map(int, input().split())
s = [list(map(str, list(input()))) for i in range(h)]
used = [[True for j in range(w)] for i in range(h)]
# used = [[True]*w]*h
for i in range(h):
    for j in range(w):
        if (s[i][j] == "#"):
            d.append([i, j])
            used[i][j] = False


ans = -1
while (d):

    tmp = deque()
    while(d):
        i, j = d.popleft()

        if i+1 < h and used[i+1][j]:
            s[i+1][j] = "#"
            tmp.append([i+1, j])
            used[i+1][j] = False

        if i-1 >= 0 and used[i-1][j]:
            s[i-1][j] = "#"
            tmp.append([i-1, j])
            used[i-1][j] = False

        if j+1 < w and used[i][j+1]:
            s[i][j+1] = "#"
            tmp.append([i, j+1])
            used[i][j+1] = False

        if j-1 >= 0 and used[i][j-1]:
            s[i][j-1] = "#"
            tmp.append([i, j-1])
            used[i][j-1] = False

    d = tmp
    ans += 1

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

def gcd(a,b):
	if a==0:
		return(b)
	return(gcd(b%a,a))
a,b=map(int,input().split())
g=gcd(a,b)

divide=2
ans=1
while(g!=1 and g!=0):
	if g%divide==0:
		ans+=1
		while(g%divide==0 and g!=0):
			g//=divide
	divide+=1
print(ans)

### FIXED CODE ###

from math import sqrt
def gcd(a,b):
	if a==0:
		return(b)
	return(gcd(b%a,a))
a,b=map(int,input().split())
g=gcd(a,b)
ans=1
if g%2==0:
	ans+=1
	while(g%2==0):
		g//=2
for divide in range(3,int(sqrt(g))+1,2):
	if g%divide==0:
		ans+=1
		while(g%divide==0):
			g//=divide
if g>2:
	ans+=1
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
lst = []
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if S[i]+S[j]+S[k] in lst:
                continue
            else:
                lst.append(S[i]+S[j]+S[k])
            if len(lst) == 999:
                print(len(lst))
                quit()
print(len(lst))

### FIXED CODE ###

N = int(input())
S = input()
lst = []
count = 0
for i in range(1000):
    num = str(i).zfill(3)
    if num[0] in S:
        a1 = S.index(num[0])
        if num[1] in S[a1+1:]:
            a2 = S[a1+1:].index(num[1]) + a1+1
            if num[2] in S[a2+1:]:
                count += 1
print(count)
### BUGGY CODE ###

#ABC116D-VariousSushi.py

import numpy as np

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
Parameters = []
Score= 0
kind = []
kindnumber = 0

ParametersAppend = Parameters.append
for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    ParametersAppend([INPUT2[0], INPUT2[1]])

Parameters = sorted(Parameters, key=lambda x: x[1], reverse=True)

def binanrySearch(kind, target):
    testkind = kind[:]
    testkind.sort()
    left, right = 0, len(testkind)-1
    while(right >= left):
        mid = int((right + left) / 2)
        if testkind[mid] == target:
            return True
        elif testkind[mid] > target:
            right = mid - 1
        elif testkind[mid] < target:
            left = mid + 1
    return False

def SearchNew(List, K, kind):
    newkind = -1
    for i in range(len(List)-K):
        if binanrySearch(kind, List[K+i][0]) == False:
            newkind = K+i
            break
    return newkind

def SearchDouble(List, K, kind):
    result = -1
    testkind = kind[:]
    testkindPop = testkind.pop
    for i in range(K):
        testkindPop(K-1-i)
        if binanrySearch(testkind, List[K-1-i][0]) == True:
            result = K-1-i
            break
    return result

kindAppend = kind.append

for i in range(K):
    kindAppend(Parameters[i][0])
kindnumber = len(set(kind))
Score = np.sum(Parameters[:K], axis=0)[1] + kindnumber**2
kind.clear()

Test1, Test2 = 0, Score

for t in Parameters:
    for i in range(K):
        kindAppend(Parameters[i][0])
    kindnumber = len(set(kind))
    i = SearchNew(Parameters, K, kind)
    j = SearchDouble(Parameters, K, kind)
    Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    if i != -1 and j != -1:
        kindnumber += 1
    else:
        break
    Test1 = Test2 - Parameters[i][1] + Parameters[j][1] + kindnumber * 2 - 1
    Test2 = Test1
    if Score <= Test2:
        Score = Test2
    kind.clear()

print(Score)


### FIXED CODE ###

#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

INPUT.sort(key = lambda x: -x[1])

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)
### BUGGY CODE ###

#ABC065

n = int(input())
a = [int(input()) for _ in range(n)]

count = 0
i = 1
while i != 2:
    i = a[i-1]
    count += 1
    if i == 1:
        print(-1)
        count = 0
        break
        
if count != 0:
    print(count)

### FIXED CODE ###

#ABC065

n = int(input())
a = [int(input()) for _ in range(n)]
b = []

i = 1
for _ in range(n):
    
    b.append(i)
    i = a[i-1]
    
    
        
if 2 in b:
    print(b.index(2))
else:
    print(-1)
### BUGGY CODE ###

N = int(input())
S1 = input()
S = [(a, p) for p, a in enumerate(S1)]
 
count = 0
for i in range(N):
    for k in range(i+1,N):
        if S[i][0] != S[k][0]:
            RGB = ['R','G','B']
            RGB.remove(S[i][0])
            RGB.remove(S[k][0])
            count += S1.count(RGB[0],k+1,N)
            if 2*k-i < N:
                if S[2*k-i][0]!= S[i][0] and S[2*k-i][0]!=S[k][0]:
                    count -= 1 
print(count)   

### FIXED CODE ###

N = int(input())
S = list(input())
count = S.count("R")*S.count("B")*S.count("G")
for i in range(N):
    for j in range(i+1,N):
        if 2*j-i < N:
            if S[i]!=S[j] and S[2*j-i]!=S[i] and S[2*j-i]!=S[j]:
                count-=1
print(count)
### BUGGY CODE ###

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

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

yaku_list = cf(A,B)
count = 1

for i in yaku_list:
  if is_prime(int(i)):
    count += 1

print(count)

### FIXED CODE ###

def dfs(n):
    table =[]
    i = 2
    while n >= i**2:
        while n % i == 0:
            if i not in table:
                table.append(i)
            n /= i
        i += 1
    if n > 1:
        table.append(int(n))
    return table

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

yaku_A = dfs(A)
yaku_B = dfs(B)
count = 1

for i in yaku_A:
  if i in yaku_B:
    count += 1

print(count)
### BUGGY CODE ###

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

modular=10**9+7
sum=0
for i in range(N):
  for j in range(i+1,N):
    #print(A[i]*A[j])
    sum+=(A[i]*A[j])%modular
    
print(sum%modular)

### FIXED CODE ###

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

modular=10**9+7
sum=0

AllSum=0
for i in range(N):
  AllSum+=A[i]
  AllSum=AllSum%modular

  
RuisekiWa=[]
NextSum=AllSum

for i in range(N):
  RuisekiWa.append((NextSum-A[i])%modular)
  NextSum=RuisekiWa[i]

#print(RuisekiWa)
for i in range(N):
  sum+=(A[i]*RuisekiWa[i])%modular
  sum=(sum%modular)
    
print(sum%modular)
### BUGGY CODE ###

a, b, n = map(int, input().split())
result = []
for i in range(10**8):
    result.append((a*n)//b - a*(n//b))
    n -= 1
    if n < 0:
        break
print(max(result))

### FIXED CODE ###

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

if b == 1:
    r = [0]
else:
    i = 0
    r = [int((a*n)/b)-a*int(n/b)]
    while b*i-1 <= n:
        r.append(int((a*(b*i-1))/b)-a*int((b*i-1)/b))
        i += 1
print(max(r))
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))

def check(a,b,c):
  return (a+b>c and b+c>a and c+a>b)

c = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    for k in range(j+1, n):
      c += 1 if check(l[i], l[j], l[k]) else 0
      
print(c)


### FIXED CODE ###

from bisect import bisect_left
 
n = int(input())
l = list(map(int, input().split()))
l.sort()
 
c = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    c += bisect_left(l, l[i]+l[j]) - j - 1
 
print(c)
### BUGGY CODE ###

n,m=map(int,input().split())
par=[-1]*n
def find(n):
    if par[n]<0:
        return n
    else:
        par[n]=find(par[n])
        return par[n]
def union(x,y):
    x,y=find(x),find(y) 
    if x!=y:
        if x>y:
            x,y=y,x
        par[x]+=par[y]
        par[y]=x
M=[]
for i in range(m):
    a,b=map(int,input().split())
    M.append([a,b])
ANS=[n*(n-1)//2]
for i in reversed(range(1,m)):
    s=n*(n-1)//2
    a,b=M[i][0],M[i][1]
    union(a-1,b-1)
    for i in range(n):
        if par[i]<-1:
            s-=par[i]*(par[i]+1)//2
    ANS.append(s)
for ans in ANS[::-1]:
    print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
par=[-1]*n
def find(n):
    if par[n]<0:
        return n
    else:
        par[n]=find(par[n])
        return par[n]
def union(x,y,s):
    x,y=find(x),find(y) 
    if x!=y:
        if x>y:
            x,y=y,x
        s-=par[x]*par[y]
        par[x]+=par[y]
        par[y]=x
    return s
        
M=[]
for i in range(m):
    a,b=map(int,input().split())
    M.append([a,b])
ANS=[n*(n-1)//2]
s=n*(n-1)//2
for i in reversed(range(1,m)):
    a,b=M[i][0],M[i][1]
    s=union(a-1,b-1,s)
    ANS.append(s)
for ans in ANS[::-1]:
    print(ans)
### BUGGY CODE ###

import numpy as np
from numba import njit

N = int(input())

sushi_count = {1:0, 2:0, 3:0}
for a in map(int, input().split()):
    sushi_count[a] += 1

expv = np.array([[[-1.0] * (sushi_count[3]+1) for i in range(N-sushi_count[1]+1)] for i in range(N+1)])

expv[0][0][0] = 0.0

@njit('f8(i8,i8,i8,f8[:,:,:])')
def get_expv(i, j, k, expv):
    result = 0.0
    if expv[i][j][k] != -1:
        return expv[i][j][k]
    nonlp = 1.0 - (N-i-j-k) / N
    result += 1
    if i != 0:
        result += get_expv(i-1, j, k, expv) * (i / N)
    if j != 0:
        result += get_expv(i+1, j-1, k, expv) * (j / N)
    if k != 0:
        result += get_expv(i, j+1, k-1, expv) * (k / N)
    result /= nonlp
    expv[i][j][k] = result
    return result

print(get_expv(sushi_count[1], sushi_count[2], sushi_count[3], expv))



### FIXED CODE ###

import numpy as np
from numba import njit


@njit('f8(i8,i8,i8,i8,f8[:,:,:])')
def get_expv(N, i, j, k, expv):
    result = 0.0
    if expv[i][j][k] != -1:
        return expv[i][j][k]
    nonlp = 1.0 - (N-i-j-k) / N
    result += 1
    if i != 0:
        result += get_expv(N, i-1, j, k, expv) * (i / N)
    if j != 0:
        result += get_expv(N, i+1, j-1, k, expv) * (j / N)
    if k != 0:
        result += get_expv(N, i, j+1, k-1, expv) * (k / N)
    result /= nonlp
    expv[i][j][k] = result
    return result

def main():
    N = int(input())

    sushi_count = {1:0, 2:0, 3:0}
    for a in map(int, input().split()):
        sushi_count[a] += 1
    sh = (N+1, N-sushi_count[1]+1, sushi_count[3]+1)
    expv = np.full(sh, -1.0)

    expv[0][0][0] = 0.0

    print(get_expv(N, sushi_count[1], sushi_count[2], sushi_count[3], expv))

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

import sys

# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    inf = 10 ** 20
    n = read_int()
    weight = {}
    adj = [[] for u in range(n)]
    for i in range(n - 1):
        a, b, c = read_int_list()
        a -= 1
        b -= 1
        adj[a].append(b)
        adj[b].append(a)
        weight[(a, b)] = c
        weight[(b, a)] = c

    q, k = read_int_list()
    k -= 1
    state = [0 for u in range(n)]
    d = [inf for u in range(n)]

    state[k] = 1
    d[k] = 0
    Q = [k]
    while Q:
        u = Q.pop(0)
        for v in adj[u]:
            if state[v] == 0:
                state[v] = 1
                d[v] = d[u] + weight[(u, v)]
                Q.append(v)
        # state[u] = 2

    res = [0] * q
    for i in range(q):
        x, y = read_int_list()
        x -= 1
        y -= 1
        res[i] = d[x] + d[y]
    print(*res, sep='\n')


main()


### FIXED CODE ###

import sys
from collections import deque


# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    n = read_int()
    adj = [[] for u in range(n+1)]
    for i in range(n - 1):
        a, b, c = map(int, input().split())
        adj[a].append((b, c))
        adj[b].append((a, c))

    d = [0] * (n+1)
    q, k = read_int_list()

    # Q = [(k, 0, 0)]
    Q = deque([(k, 0, 0)])
    while Q:
        u, parent, dist = Q.popleft()
        for v, w in adj[u]:
            if v != parent:
                Q.append((v, u, dist+w))
        d[u] = dist

    res = [0] * q
    for i in range(q):
        x, y = map(int, input().split())
        res[i] = d[x] + d[y]
    print(*res, sep='\n')


main()
### BUGGY CODE ###

a, b, k = map(int, input().split())
ans = []
pool = [i for i in range(a, b+1)]
ans += pool[:k] + pool[-k:]
ans = list(set(ans))
ans.sort()
[print(i) for i in ans]


### FIXED CODE ###

a, b, k = map(int, input().split())
ans = []
for i in range(a, min(a+k, b)):
    ans.append(i)
for i in range(max(b-k+1, a), b+1):
    ans.append(i)
ans = sorted(list(set(ans)))
for i in ans:
    print(i)
### BUGGY CODE ###

N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
px = [list(map(int, input().split())) for _ in range(Q)]

graph = [[] for _ in range(N)]
for ai, bi in ab:
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

parent = [None] * N
parent[0] = 0

import sys
sys.setrecursionlimit(200002)

# def dfs(src):
#     for dst in graph[src]:
#         if parent[dst] != None: continue
#         #
#         parent[dst] = src
#         dfs(dst)

# dfs(0)
# print("#", parent)

score = [0] * N
for pi, xi in px:
    score[pi - 1] += xi
        
memo = [None] * N

# def dp(arg):
#     if memo[arg] != None: return memo[arg]
#     #
#     # print("#", arg)
#     ret = score[arg]
#     if arg != parent[arg]: ret += dp(parent[arg])
#     memo[arg] = ret
#     return ret

ans = [None] * N

def set_score(src, score_tmp):
    score_tmp += score[src]
    ans[src] = score_tmp
    for dst in graph[src]:
        if ans[dst] != None: continue
        set_score(dst, score_tmp)
        
set_score(0, 0)        

# ans = []
# for i in range(N):
#     ans.append(dp(i))

# print("#", memo)

print(' '.join(map(str, ans)))

### FIXED CODE ###

N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
px = [list(map(int, input().split())) for _ in range(Q)]

graph = [[] for _ in range(N)]
for ai, bi in ab:
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

parent = [None] * N
parent[0] = 0

score = [0] * N
for pi, xi in px:
    score[pi - 1] += xi

ans = [None] * N

from collections import deque

q = deque([(0, 0)])
while len(q) > 0:
    src, score_tmp = q.popleft()
    score_tmp += score[src]
    ans[src] = score_tmp
    for dst in graph[src]:
        if ans[dst] != None: continue
        q.append((dst, score_tmp))

print(' '.join(map(str, ans)))