Harryxun/stf_run huggingface dataset:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
dg={i:[[],0] for i in range(1,N+1)}
for i in range(1,N):
    a,b=map(int,input().split())
    dg[a][0].append(b)
    dg[b][0].append(a)
#print(dg)
def habatan(p,me):
    if me!=1:
        dg[me][0].remove(p)
    for c in dg[me][0]:
        habatan(me,c)

habatan(0,1)#dg親消し
#print(dg)
#dv={i:0 for i in range(1,N+1)}
for i in range(Q):
    p,x=map(int,input().split())
    #dv[p]+=x
    dg[p][1]+=x
#dans={}
def habatan1(p,me):
    if me!=1:
        #dv[me]+=
        dg[me][1]+=dg[p][1]
    #for c in dg[me]:
    for c in dg[me][0]:
        habatan1(me,c)
habatan1(0,1)
for i in range(1,N+1):
    #print(dv[i],end=" ")
    print(dg[i][1],end=" ")
print("")


### FIXED CODE ###

#import collections
N,Q=map(int,input().split())
lc=[[] for i in range(N)]#二重リストで木を表現
for i in range(N-1):
    a,b=map(int,input().split())
    lc[a-1].append(b-1)
    lc[b-1].append(a-1)
lv=[0 for i in range(N)]#値のリスト
for i in range(Q):
    p,x=map(int,input().split())
    lv[p-1]+=x
lf=[0 for i in range(N)]#訪れたかどうか
#d=collections.deque([0])
lp=[0]
lf[0]=1
#for i in range(N):
while len(lp)>0:
    #p=lp[-1]
    p=lp.pop()
    for c in lc[p]:
        if lf[c]==0:
            lv[c]+=lv[p]
            lf[c]=1
            lp.append(c)
for i in range(N-1):
    print(lv[i],end=" ")
print(lv[N-1])
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        if len(que) > 0:
         for j in len(que):
          if len(que) > 0:
        #while len(que) > 0:
            u[j] = que[0]
            for v in graph[u[j]]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1
q = int(raw_input())
for i in range(q):
    s,t = map(int,raw_input().strip().split(' '))
    if color[s] == color[t]:
        print 'yes'
    else:
        print 'no'

### FIXED CODE ###

n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        while len(que) > 0:
            u = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1
q = int(raw_input())
for i in range(q):
   s,t = map(int,raw_input().strip().split(' '))
   if color[s] == color[t]:
     print 'yes'
   else:
     print 'no'
w=list(input())
now=0
num=len(w)
w.append(" ")
count=0
while now<num:
  if w[now]!="A":
    now+=1
  else:
    if w[now+1]!="B":
      now+=1
    else:
      if w[now+2]!="C":
        now+=1
      else:
        w[now]="B"
        w[now+1]="C"
        w[now+2]="A"
        count+=1
        back=now-1
        b=True
        while back>0 and b=True:
          if w[back]!="A":
            b=False
          else:
            w[back]="B"
            w[back+1]="C"
            w[back+2]="A"
            count+=1
            back-=1
print(count)
            

### FIXED CODE ###

w=input()
count=0
num=len(w)
w1=""
w+=" "
while count<num:
  if w[count]=="A":
    w1+="A"
    count+=1
  elif w[count]=="B":
    if w[count+1]=="C":
      w1+="D"
      count+=2
    else:
      w1+="B"
      count+=1
  else:
    w1+="C"
    count+=1
counta=0
ans=0
num=len(w1)
for i in range(num):
  if w1[i]=="A":
    counta+=1
  elif w1[i]=="D":
    ans+=counta
  else:
    counta=0
print(ans)
#157 b
a=[]
call_num=[]
for i in range(3):
    x,y,z=map(int,input().split())
    a.append(x)
    a.append(y)
    a.append(z)
n=int(input())
for i in range(n):
    x=int(input())
    if x in a:
        call_num.append(a.index(x))
bingo
ans=[[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
for x in ans:
    flag=True
    for y in x:
        if y not in call_num:
            flag=False
    if flag:
        print("Yes")
        bing=True
        break
if bingo!=True:        
    print("No")


### FIXED CODE ###

#157 b
a=[]
call_num=[]
for i in range(3):
    x,y,z=map(int,input().split())
    a.append(x)
    a.append(y)
    a.append(z)
n=int(input())
for i in range(n):
    x=int(input())
    if x in a:
        call_num.append(a.index(x))
bingo=False
ans=[[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
for x in ans:
    flag=True
    for y in x:
        if y not in call_num:
            flag=False
    if flag:
        print("Yes")
        bingo=True
        break
if bingo!=True:
    print("No")
import math
r = int(input())
print(3.14, 3.14)

### FIXED CODE ###

import math
r = float(input())
print(r * r * math.pi, 2 * r * math.pi)
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from collections import defaultdict
import json
from copy import deepcopy

def dfs(graph, s, d, count=0):
  if len(graph[s]) == 0:
    d[s] = count
  for t in graph[s]:
    if s in graph[t]:
      graph[t].remove(s)
    dfs(graph, t, d, count+1)

if __name__=='__main__':
  graph = defaultdict(list)
  n, u, v = map(int, input().strip().split())
  for _ in range(n-1):
    ai, bi = map(int, input().strip().split())
    graph[ai].append(bi)
    graph[bi].append(ai)
  du, dv = dict(), dict()
  du[u], dv[v] = 0, 0
  dfs(deepcopy(graph), u, du)
  dfs(deepcopy(graph), v, dv)

  costv = [0]
  for k in dv.keys():
    if k in du and du[k] < dv[k]:
      costv.append(dv[k])
  print(max(costv) - 1)

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from collections import defaultdict
import json
from copy import deepcopy
import sys
sys.setrecursionlimit(10**4)

def dfs(graph, s):
  dist = [-1 for _ in range(len(graph))]
  dist[s] = 0
  stack = [s]
  while len(stack) != 0:
    s = stack.pop()
    for t in graph[s]:
      dist[t] = dist[s]+1
      if s in graph[t]:
        graph[t].remove(s)
      stack.append(t)
  return dist

if __name__=='__main__':
  graph = defaultdict(list)
  n, u, v = map(int, input().strip().split())
  for _ in range(n-1):
    ai, bi = map(int, input().strip().split())
    graph[ai-1].append(bi-1)
    graph[bi-1].append(ai-1)
  du = dfs(deepcopy(graph), u-1)
  dv = dfs(deepcopy(graph), v-1)
  costv = [0]
  for duv, dvv in zip(du, dv):
    if duv < dvv:
      costv.append(dvv)
  print(max(costv) - 1)
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
sumc = 0

for count in range(N-1):
    if A[count+1] - A[count] == 1:
        sumc = sumc + C[A[count]-1]

print(sumc + sum(B))


### FIXED CODE ###

N = int(input())

print(N*N*N)
#!/usr/bin/env python3

def solve(N, d):
    total = 0
    for i1 in range(len(d)):
        for i2 in range(i1+1, len(d)):
            total += d[i1] * d[i2]
    return total


if __name__ == '__main__':
    N = int(input())
    d = map(int, input().split())

    ans = solve(N, list(d))

    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3


def solv(n, d):
    ll = d * 2 + 1
    ans = (n + ll - 1) // ll
    return ans


if __name__ == '__main__':

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

    ans = solv(n, d)

    print(ans)
l = map(int, raw_input().split())

print(l[0]*l[1])



### FIXED CODE ###


1
2
a, b = map(int, input().split())
print(str(a * b) + " " + str(2 * a + 2 * b))
c = input() 
msg = 'vowel' if ((c == 'a') or (c == 'i') or (c == 'u') or (c == 'e') or (c == 'o')) else 'consonant':
print(msg)

### FIXED CODE ###

print(['vowel','consonant'][not input() in ['a','e','i','o','u']])
n = int(raw_input())
s = ["" for i in range(n)]

while True:
    a = raw_input().split()
    if a[0] == "quit":
        break

    i = int(a[1])
    if a[0] == "push":
        s[i] += a[2]

    elif a[0] == "pop":
        l = len(s[i]) - 1
        print s[i][l]
        s[i] = s[i][:l]

    elif a[0] == "move":
        j = int(a[2])
        l = len(s[i]) - 1
        s[j] += s[i][l]
        s[i] = s[i][:l]

### FIXED CODE ###

n = int(raw_input())
s = ["" for i in range(n)]

while True:
    a = raw_input().split()
    if a[0] == "quit":
        break

    i = int(a[1]) - 1
    if a[0] == "push":
        s[i] += a[2]

    elif a[0] == "pop":
        l = len(s[i]) - 1
        print s[i][l]
        s[i] = s[i][:l]

    elif a[0] == "move":
        j = int(a[2]) - 1 
        l = len(s[i]) - 1
        s[j] += s[i][l]
        s[i] = s[i][:l]
n=input()
a=[]
for i in range(1,10**5):
  a+=i
  if a>=n:
    break
print(i_

### FIXED CODE ###

n=int(input())
a=0
for i in range(1,10**5):
  a+=i
  if a>=n:
    break
print(i)
n=input()
a=[int(i) for i in input().split()]

import math
from functools import reduce

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

g=lcm(*a)-1

ans=0
for i in a:
    ans+=g%i

print(ans)


### FIXED CODE ###

n=input()
a=[int(i) for i in input().split()]
ac=a[:]


def lcm(x, y):
    x2=x
    y2=y
    while y != 0:
        x, y = y, x%y
    return (x2 * y2) // x

while(len(ac)>1):
    x=ac.pop()
    y=ac.pop()
    ac.append(lcm(x, y))

g=ac[0]-1

ans=0
for i in a:
    ans+=g%i

print(ans)
x=int(input()
y=int(input()
z=int(input()
print((x+y)*z/2)

### FIXED CODE ###

x=int(input())
y=int(input())
z=int(input())
print(round((x+y)*z/2))
from sys import stdin
moji=(stdin.readline().rstrip())
N=int(stdin.readline().rstrip())
ans=moji[0]
for i in range(1,len(moji)):
    if i*N > len(moji):
        break
    ans=ans+moji[i*N]
print(ans)

### FIXED CODE ###

from sys import stdin
moji=(stdin.readline().rstrip())
N=int(stdin.readline().rstrip())
ans=moji[0]
ite=len(moji)
for i in range(1,ite+1):
    if i*N > len(moji)-1:
        break
    ans=ans+moji[i*N]
print(ans)
s = input()
K = int(input())
S = []
for i in range(1, len(s) + 1):
    k = 0
    while True:
        if len(s) - k - i < 0:
            break
        a = []
        for j in range(0, i):
            a.append(s[j + k])
        S.append(a)
        k += 1

keylist = []
for i in range(len(S)):
    for j in range(len(S)):
        if S[i] == S[j] and i != j and i > j:
            keylist.append(i)

for i in keylist:
    del S[i]
S.sort()
print(''.join(S[K - 1]))

### FIXED CODE ###

s = list(input())
K = int(input())
j = 0
candidate = []
while True:
    if j > 26:
        break
    for i in range(len(s)):
        if s[i] == chr(ord("a") + j):
            for k in range(1, min(6, len(s) - i + 1)):
                candidate.append(s[i:i + k])
    j += 1
i = 1
candidate.sort()
while i < len(candidate):
    if candidate[i] == candidate[i - 1]:
        del candidate[i]
        i -= 1
    i += 1

for i in candidate[K - 1]:
    print(i, end = "")
print()
from collections import Counter as co
n=int(input())
l=sorted(list(map(list,co(map(int,input().split())).items())))
if if l[0][0]==0 and l[0][-1]>1:print(0);exit()
ans=1;pre=1
for i,(n,s) in enumerate(l):
  if i!=n:print(0);exit()
  if i>1:
    ans*=(pre**s)
    ans%=998244353
  pre=s
print(ans)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
if l[0]:print(0);exit()
mod=998244353
k=[0]*n
for i in l:k[i]+=1
if k[0]!=1:print(0);exit()
ans=1
for i,s in zip(k,k[1:]):ans*=pow(i,s,mod)
print(ans%mod)
w=input()
ll=list()
while True:
    T=input()
    T=T.lower()
    if T=="END_OF_TEXT":
        break
    t=T.split()
    for i in t:
        ll.append(i)
ans=ll.count(w)
print(ans)



### FIXED CODE ###

w=input()
ll=list()
while True:
    T=input()
    if T=="END_OF_TEXT":
        break
    T=T.lower()
    t=T.split()
    for i in t:
        ll.append(i)
ans=ll.count(w)
print(ans)
import sys
input = sys.stdin.readline

def main():
    H,W = map(int,input().split())
    a = [list(map(int,input().split())) for _ in range(H)]

    for i in range(H):
        for j in range(W-1):
            if a[i][j]%2 == 1:
                print(i+1,j+1,i+1,j+2)
            a[i][j+1] += a[i][j]

    for i in range(H-1):
        if a[i][-1]%2 == 1:
            print(i+1,j+1,i+2,j+1)
        a[i+1][-1] += a[i][-1]

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    H,W = map(int,input().split())
    a = [list(map(int,input().split())) for _ in range(H)]
    
    ans = []
    for i in range(H):
        for j in range(W-1):
            if a[i][j]%2 != 0:
                a[i][j+1] += 1
                ans.append((i+1,j+1,i+1,j+2))
                
    for i in range(H-1):
        if a[i][-1]%2 != 0:
            a[i+1][-1] += 1
            ans.append((i+1,W,i+2,W))
            
    print(len(ans))
    for x in ans:
        print(*x)

if __name__ == "__main__":
    main()
import collections
S = input()
S2 = collections.counter(S)
c = True
for i,v in S2.items():
  if v == 2:
    continue
  else:
    c = False
if c:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import collections
S = input()
S2 = collections.Counter(S)
c = True
for i,v in S2.items():
  if v == 2:
    continue
  else:
    c = False
if c:
  print('Yes')
else:
  print('No')
def dfs(G, s, dist):
    for v in G[s]:
        if dist[v] > dist[s] + 1:
            dist[v] = dist[s] + 1
            dfs(G, v, dist)

N, M = map(int,input().split())

G = [[] for _ in range(3*N)]

for _ in range(M):
    u, v = map(int,input().split())
    u, v = u-1, v-1

    G[u].append(v+N)
    G[u+N].append(v+2*N)
    G[u+2*N].append(v)

s, t = map(int,input().split())
s, t = s-1, t-1

dist = [10**9] * (3*N)
dist[s] = 0

dfs(G, s, dist)

if dist[t] == 10**9:
    print(-1)
else: 
    print(dist[t] // 3)

### FIXED CODE ###

from collections import deque
INF = 10**9

N, M = map(int,input().split())

G = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int,input().split())
    u, v = u-1, v-1

    G[u].append(v+N)
    G[u+N].append(v+2*N)
    G[u+2*N].append(v)

s, t = map(int,input().split())
s, t = s-1, t-1

dist = [INF] * (3*N)
dist[s] = 0

Q = deque([s])
while len(Q) > 0:
    u = Q.popleft()
    for v in G[u]:
        if dist[v] == INF:
            dist[v] = dist[u] + 1
            Q.append(v)

if dist[t] == INF:
    print(-1)
else: 
    print(dist[t] // 3)
import decimal
a,b=map(str,input().split())
c=decimal.Decimal(a)*decimal.Decimal(b)
print(decimal.Decimal(str(c)).quantize(decimal.Decimal('0'),rounding=ROUND_FLOOR))

### FIXED CODE ###

from decimal import Decimal,ROUND_FLOOR
a,b=map(str,input().split())
c=Decimal(a)*Decimal(b)
print(Decimal(str(c)).quantize(Decimal('0'),rounding=ROUND_FLOOR))
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [-1]+a
v = [-1 for _ in range(n+1)]
v[1] = 0
x = a[1]
c = 0
while k > 0 and v[x] < 0:
    y = a[x]
    v[y] = v[x]+1
    x = y
    k -= 1
    c += 1

if k==0:
    print(x)
else:
    z = c - v[x]
    if z != 0:
        k = k%z
    else:
        k = k%c
    while k > 0:
        k -= 1
        x = a[x]
    print(x)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [i-1 for i in a]
v = [-1 for _ in range(n)]
p = 0
x = 0
c = 0
while k > 0 and v[x] < 0:
    v[x] = p+1
    p = v[x]
    x = a[x]
    c += 1
    k -= 1

z = c-v[x]+1
k = k%z

while k > 0:
    k -= 1
    x = a[x]
print(x+1)
K=input()
r='ACL'
for i in range(1,int(k)):
  r='ACL'+ r 
print(r)

### FIXED CODE ###

K=input()
r='ACL'
for i in range(1,int(K)):
  r='ACL'+ r 
print(r)
import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,i = na()
a = na()
dp = [i for i in a]
ans = sum(dp)

for i in range(1,n):
    for j in range(n):
        dp[(j+i)%n] = min(dp[(j+i)%n], a[j])
    ans = min(ans, sum(dp)+x*i)

print(ans)

### FIXED CODE ###

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

n,x = na()
a = na()
dp = [i for i in a]
ans = sum(dp)

for i in range(1,n):
    for j in range(n):
        dp[(j+i)%n] = min(dp[(j+i)%n], a[j])
    ans = min(ans, sum(dp)+x*i)

print(ans)
from math import gcd
    

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

p = 10**9
for i in range(N-1) :
    q = gcd(L[i],L[i+1])
    if q < p :
        p = q

if K % p ==  0 :
    ans = "POSSIBLE"
else :
    ans = "IMPOSSIBLE"
print(ans)


### FIXED CODE ###

def gcd(a,b) :
    while b :
        a,b = b, a % b
    return a

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

if len(L) == 1 :
    if L[0] == K :
        ans = "POSSIBLE"
    else :
        ans = "IMPOSSIBLE"

else :
    for i in range(N-1) :
        q = gcd(L[i],L[i+1])
        if i == 0 :
            p = gcd(L[i],L[i+1])
        if q < p :
            p = q

    if (K % p ==  0) and (K <= max(L)) :
        ans = "POSSIBLE"
    else :
        ans = "IMPOSSIBLE"
print(ans)
n , m = map(float ,input().split())
n = int(n)
ans = str(n * (m * 100)) / 100

print(ans[:ans.find('.')])

### FIXED CODE ###

a, b = input().split()
a = int(a)
b = int(b.replace(".",""))

c = a * b
ans = c//100
print(ans)
N = int(input())
points = list(map(int, input().split(" ")))

powers = []
for i in range(min(points), max(points)):
    power = 0
    for point in points:
        power += ((i - point) ** 2)
    powers.append(power)
print(min(powers))


### FIXED CODE ###

N = int(input())
points = list(map(int, input().split(" ")))

powers = []
for i in range(min(points), max(points) + 1):
    power = 0
    for point in points:
        power += ((i - point) ** 2)
    powers.append(power)

print(min(powers))
def k(n):
    mod =1000000007
    if n==1:
        return 1
    else:
        return (n*k(n-1))%mod
print(k(int(input())))


### FIXED CODE ###

n=1
for i in range(1,int(input())+1):
    n*=i
    n=n%1000000007
print(n)
def main():
    n,m = map(int,input().split())
    job =[[] for _ in range(m)]
    for i in range(n):
        a,b=map(int,input().split())
        if a-1 < m:
            job[d-1].append(-r) # r:asc, -r:desc
    
    res = 0
    q = 0
    from heapq import heappop, heappush
    for i in range(m):
        for j in job[i]:
            heappush(q, j)
        if len(q) < 0:
            res += heappop(q) * -1 # -r -> r
    print(res)

if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    n,m = map(int,input().split())
    job =[[] for _ in range(m)]
    for i in range(n):
        a,b=map(int,input().split())
        if a-1 < m:
            job[a-1].append(-b) # b:asc, -b:desc
    
    res = 0
    q = []
    from heapq import heappop, heappush
    for i in range(m):
        for j in job[i]:
            heappush(q, j)
        if len(q) > 0:
            res += heappop(q) * -1 # -b -> b
    print(res)

if __name__ == '__main__':
    main()
N = int(input())
S = input()

ans = 0
c = 0
for i in range(N):
    c = len(set(list(S[:i]))&set(list(S[i:])))
    ans = max(ans,c)
print(ans)

### FIXED CODE ###

a,b = map(int,input().split())
print(max(a+b,a-b,a*b))
n=int(input())
s=list(input())
num=0
if n<3:
    exit()
for i in range(n):
    if (s[i]=="A") and (s[i+1]=="B") and (s[i+2]=="C"):
        num+=1
print(num)


### FIXED CODE ###

n=int(input())
s=list(input())
num=0
if n<3:
    exit()
for i in range(n-2):
    if (s[i]=="A") and (s[i+1]=="B") and (s[i+2]=="C"):
        num+=1
print(num)
import math
import collections
import fractions
import itertools
import functools
import operator

def solve():
    l, r, d = map(int, input().split())
    ans = 0
    for i in range(l, r+1):
        if i % d == 0:
            ans += 1
    priht(ans)
    return 0

if __name__ == "__main__":
    solve()



### FIXED CODE ###

import math
import collections
import fractions
import itertools
import functools
import operator

def solve():
    l, r, d = map(int, input().split())
    ans = 0
    for i in range(l, r+1):
        if i % d == 0:
            ans += 1
    print(ans)
    return 0

if __name__ == "__main__":
    solve()
x,a,b=map(int,input().split)
if(a-b>=0):
  print('delicious')
elif(b-a<=x):
  print('safe')
else:
  print('dangerous')

### FIXED CODE ###

x,a,b=map(int,input().split())
if(a-b>=0):
  print('delicious')
elif(b-a<=x):
  print('safe')
else:
  print('dangerous')
n = int(input())

d = [0 for i in range(n+1)]
adj = [[] for i in range(n+1)]

def dfs(u, par):
    for p in adj[u]:
        v, w = map(int, p)
        # print(v, w)
        if v != par:
            d[v] = d[u]+w
            dfs(v, u)

edge = [list(map(int, input().split())) for i in range(n-1)]
q, k = map(int, input().split())
query = [list(map(int, input().split())) for i in range(q)]

for e in edge:
    adj[e[0]].append([e[1], e[2]])
    adj[e[1]].append([e[0], e[2]])
    
dfs(k, -1)

for p in query:
    print(d[p[0]]+d[p[1]])

### FIXED CODE ###

n = int(input())
edge = [list(map(int, input().split())) for i in range(n-1)]
q, k = map(int, input().split())
query = [list(map(int, input().split())) for i in range(q)]

d = [0 for i in range(n+1)]
visited = [False for i in range(n+1)]
adj = [[] for i in range(n+1)]

for e in edge:
    adj[e[0]].append([e[1], e[2]])
    adj[e[1]].append([e[0], e[2]])
    
st = [k]
visited[k] = True
while st:
    u = st.pop()
    for p in adj[u]:
        v, w = map(int, p)
        if not visited[v]:
            visited[v] = True
            d[v] = d[u]+w
            st.append(v)

for p in query:
    print(d[p[0]]+d[p[1]])
import math
n = int(input())
m = int(math.sqrt(n))

ans = n - 1

for a in range(m):
  if n % a == 0:
    b = n // a
    ans = min(ans, a + b - 2)
    
print(ans)

### FIXED CODE ###

import math
n = int(input())
m = int(math.sqrt(n)) + 1

ans = n - 1

for a in range(2, m):
  if n % a == 0:
    ans = min(ans, a + n//a - 2)
    
print(ans)
#Resistors in Parallel
N = int(input())
lst_A = [1/int(input()) for i in range(N)]

print(1/sum(lst_A))

### FIXED CODE ###

n = input()
lst_A = map(int, input().split())
lst_A_inv = [1/x for x in lst_A]
print(1/sum(lst_A_inv))
H,W = (int(i) for i in input().split())

original = [input() for i in range(H)]
sujimaru = [[0 for i in range(W+2)for j in range(H+2)]]

for j in range(H):
    for i in range(W):
        if(original[i][j] == "#"):
            sujimaru[i][j] += 1
            sujimaru[i+1][j] += 1
            sujimaru[i+2][j] += 1
            sujimaru[i][j+1] += 1
            sujimaru[i+2][j+1] += 1
            sujimaru[i][j+2] += 1
            sujimaru[i+1][j+2] += 1
            sujimaru[i+2][j+2] += 1

d = [""]*H
for j in range(H):
    for i in range(W):
        if(original[j][i] == "."):
            d[j] += str(sujimaru[j+1][i+1])
        else:
            d[j] += "#"

for s in d:
    print(s)

### FIXED CODE ###

H,W = (int(i) for i in input().split())

#囲い付きで入力　上下左右斜めを確認するとき用
firstline = "*"*(W+2)
bomb = [firstline]
for i in range(H):
    line = "*" + input() + "*"
    bomb.append(line)
lastline = "*"*(W+2)
bomb.append(lastline)

#答えの配列
answer = [[0]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        if bomb[i+1][j+1] == "#":
            answer[i][j] = "#"
        else:
            if bomb[i+1+1][j+1+1] == "#":
                answer[i][j] += 1
            if bomb[i+1+1][j+1+0] == "#":
                answer[i][j] += 1
            if bomb[i+1+1][j+1-1] == "#":
                answer[i][j] += 1
            if bomb[i+1+0][j+1+1] == "#":
                answer[i][j] += 1
            if bomb[i+1+0][j+1-1] == "#":
                answer[i][j] += 1
            if bomb[i+1-1][j+1+1] == "#":
                answer[i][j] += 1
            if bomb[i+1-1][j+1+0] == "#":
                answer[i][j] += 1
            if bomb[i+1-1][j+1-1] == "#":
                answer[i][j] += 1

#print(answer)
for i in range(H):
    tmp = ""
    for j in range(W):
        tmp += str(answer[i][j])
    print(tmp)