Harryxun/stf_run huggingface dataset:
import sys

parents = [-1] * 20000

def main():

    input = sys.stdin.readline

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


    for _ in range(M):
        A,B = map(int,input().split())

        A = A - 1
        B = B - 1

        union(A,B)

    ans = 1
    for i in range(N):
        ans = max(ans,size(i))

    print(ans)

def find(x):
    if parents[x] < 0:
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]

def union(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return

    if parents[x] > parents[y]:
        x, y = y, x

    parents[x] += parents[y]
    parents[y] = x

def size(x):
    return -parents[find(x)]


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys


def main():

    input = sys.stdin.readline

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

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

    UF = UnionFind(N)

    for i in range(M):
        A,B = AB[i]

        A = A - 1
        B = B - 1

        UF.union(A,B)


    ans = 1
    for i in range(N):
        ans = max(ans,UF.size(i))

    print(ans)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

if __name__ == "__main__":
    main()
def gcd(a,b):
    if b > a:
        a, b = b, a
    while b:
        a, b = b, a%b
    return a

N = int(input())
T = list(map(int,input().split()))
LIS = []
for i in range(N-1):
    A = gcd(T[i],T[i+1])
    LIS.append(A)
F = LIS.index(min(LIS))
T.pop(F+1)
LIS = []
for i in range(N-2):
    A = gcd(T[i],T[i+1])
    LIS.append(A)
print(min(LIS))

### FIXED CODE ###

import copy 

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

N = int(input())
T = list(map(int,input().split()))
T.sort()
LIS = [0]*N
LIS[0] += T[0]
for i in range(N-1):
    LIS[i+1] += gcd(LIS[i],T[i+1])
F = LIS.index(min(LIS))
if len(T) == 2:
    ANS = max(T[0],T[1])
elif F == 0:
    U = copy.copy(T)
    V = copy.copy(T)
    U.pop(1)
    V.pop(0)
    LU = [0]*(N-1)
    LU[0] = U[0]
    LV = [0]*(N-1)
    LV[0] = V[0]
    for i in range(N-2):
        LU[i+1] += gcd(LU[i],U[i+1])
    ANSU = LU[N-2]
    for i in range(N-2):
        LV[i+1] += gcd(LV[i],V[i+1])
    ANSV = LV[N-2]
    ANS = max(ANSU,ANSV)
    
else:
    U = copy.copy(T)
    V = copy.copy(T)
    U.pop(F)
    V.pop(0)
    LU = [0]*(N-1)
    LU[0] = U[0]
    LV = [0]*(N-1)
    LV[0] = V[0]
    ANSU = 0
    ANSV = 0
    for i in range(N-2):
        LU[i+1] += gcd(LU[i],U[i+1])
    ANSU = LU[N-2]
    for i in range(N-2):
        LV[i+1] += gcd(LV[i],V[i+1])
    ANSV = LV[N-2]
    ANSP = max(ANSU,ANSV)
    ANS = max(ANSP,LIS[N-1])
        
print(ANS)
x, a, b = int(input().split())
if a >= b:
    print("delicious")
elif (b - a) <= x:
    print("safe")
else:
    print("dangerous")

### FIXED CODE ###

x, a, b = map(int, input().split())
if a >= b:
    print("delicious")
elif (b - a) <= x:
    print("safe")
else:
    print("dangerous")
a,b,c=map(int, input.split())
print(str(z x y))

### FIXED CODE ###

x,y,z=map(int,input().split())
print(str(z)+" "+str(x)+" "+str(y))
import sys
import os
sys.setrecursionlimit(10000000000000)

def lcm(x,y):
    return (x*y)//gcd(x,y)

def gcd(x,y):
    if y <= 0:
        return x
    else:
        return gcd(y,x%y)

N = int(input())
T = [int(input()) for _ in range(N)]
ans = lcm(T[0],T[1])
for i in range(2,N):
    ans = lcm(ans,T[i])
print(ans)


### FIXED CODE ###

import sys
import os
sys.setrecursionlimit(100000000)

def lcm(x,y):
    return (x*y)//gcd(x,y)

def gcd(x,y):
    if y <= 0:
        return x
    else:
        return gcd(y,x%y)

N = int(input())
T = [int(input()) for _ in range(N)]
if N == 1:
    print(T[0])
    sys.exit()

ans = lcm(T[0],T[1])
for i in range(2,N):
    ans = lcm(ans,T[i])
print(ans)
import numpy as np

input()
l = list(map(int, input().split()))
m = np.lcm.reduce(l) - 1

ans = 0
for i in range(len(l)):
	ans += m % l[i]

print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
print(sum(l) - n)
n,m=map(int,input().split())
a=[]
for i in range(0,n):
  b,c=map(int.input().split())
  a.append[b,c]
a.sort()
number=0
for i in range(0,len(a)):
  while number<m:
    number=number+a[i][1]
    l=i
answer=0
kosu=0
for k in range(0,l-1):
  answer=answer+a[k][0]*a[k][1]
  kosu=kosu+a[k][1]
answer=answer+a[l][0]*(m-kosu)
print(answer)

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
for i in range(0,n):
    b,c=map(int,input().split())
    a.append([b,c])
a.sort()
number=0
for i in range(0,len(a)):
    if number<m:
        number=number+a[i][1]
        l=i
answer=0
kosu=0
for k in range(0,l):
    answer=answer+a[k][0]*a[k][1]
    kosu=kosu+a[k][1]
answer=answer+a[l][0]*(m-kosu)
print(answer)
import queue
from itertools import product

H, W = map(int, input().split())
road_grid = [row for row in input()]

# for each start point, find the furthest travellable point
# then return largest path length of all these
# ps y is down, x is right
furthest_so_far = -1
for y_init, x_init in product(range(H), range(W)):
    if road_grid[y_init][x_init] == "#": continue
    boundary = queue.Queue()
    boundary.put((y_init, x_init))
    steps_taken = [[-1]*W for _ in range(H)]
    steps_taken[y_init][x_init] = 0
    while not boundary.empty():
        y, x = boundary.get()
        neighbours = [(y+1, x), (y, x+1), (y-1, x), (y, x-1)]
        for (new_y, new_x) in neighbours:
            if (0 <= new_y < H and 0 <= new_x < W
                and steps_taken[new_y][new_x] == -1 and road_grid[new_y][new_x] == "."):
                steps_taken[new_y][new_x] = steps_taken[y][x] + 1
                boundary.put((new_y, new_x))
    furthest_so_far = max(furthest_so_far, max(max(steps_taken)))
print(furthest_so_far)


### FIXED CODE ###

x = input()
print(chr(ord(x)+1))
import itertools
 
H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(map(int, input().split())))
 
ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    cnt = t.count(1)
    lst = [[s for s in S[0]]]
    for h in range(H - 1):
        if t[h]:
            lst.append(S[h + 1])
        else:
            lst[-1] = [lst[-1][i] + S[h + 1][i] for i in range(W)]
    L = len(lst)
    sum_lst = [0] * L
    for w in range(W):
        if max(lst[i][w] for i in range(L)) > K:
            break
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        if max(tmp) > K:
            cnt += 1
            sum_lst = [lst[i][w] for i in range(L)]
        else:
            sum_lst = tmp
    else:
        ans = min(ans, cnt)
print(ans)

### FIXED CODE ###

import itertools
 
H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append([int(s) for s in input()])
 
ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    cnt = t.count(1)
    lst = [[s for s in S[0]]]
    for h in range(H - 1):
        if t[h]:
            lst.append(S[h + 1])
        else:
            lst[-1] = [lst[-1][i] + S[h + 1][i] for i in range(W)]
    L = len(lst)
    sum_lst = [0] * L
    for w in range(W):
        if max(lst[i][w] for i in range(L)) > K:
            break
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        if max(tmp) > K:
            cnt += 1
            sum_lst = [lst[i][w] for i in range(L)]
        else:
            sum_lst = tmp
    else:
        ans = min(ans, cnt)
print(ans)
N = int(input())
p = map(int, input().split())
cnt = 0

for i in range(1,1+N):
  if p[i]+1 != p[i+1]:
    cnt += 1

if cnt <= 3:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

N = int(input())
p = list(map(int, input().split()))
cnt = 0
 
for i in range(N):
  if p[i] != i+1:
    cnt += 1
 
if cnt==0 or cnt==2 :
  print('YES')
else:
  print('NO')
s = list(input())
t = list(input())
ing_total = 0

for x in range(2):
    if s[x] == t[x]:
        ing_total+=1
    print(ing_total

### FIXED CODE ###

s = list(input())
t = list(input())
ing_total = 0

for x in range(3):
    if s[x] == t[x]:
        ing_total+=1
    else:
        ing_total+=0
print(ing_total)
N = int(input())
alphabet = [chr(i) for i in range(97, 97+26)]

n = 1
s = 26
for i in range(1,12):
    if N <= s:
        n = i
        break
    else:
        s += 26**(i+1)
        
s = 0
for i in range(1,n):
    s += 26**i
    
N = N - s - 1
if N == 0:
    Ans = ""
    for _ in range(n):
        Ans += "a"
else:
    while N > 0:
        L.append(N%26)
        N = N//26
    
    Ans = ""
    for x in reversed(L):
        Ans += alphabet[x]
print(Ans)

### FIXED CODE ###

N = int(input())
alphabet = [chr(i) for i in range(97, 97+26)]

n = 1
s = 26
for i in range(1,12):
    if N <= s:
        n = i
        break
    else:
        s += 26**(i+1)
        
s = 0
for i in range(1,n):
    s += 26**i
    
N = N - s - 1
if N == 0:
    Ans = ""
    for _ in range(n):
        Ans += "a"
else:
    L = [0 for _ in range(n)]
    i = 1
    while N > 0:
        L[-i] = N%26
        N = N//26
        i +=1
    
    Ans = ""
    for x in L:
        Ans += alphabet[x]
print(Ans)
a = [input() for i in range(5)]
print (6-a[0]-a[1])

### FIXED CODE ###

A = input()
B = input()
print(6-int(A)-int(B))
s = []
s = map(int, input().split())
print(s[0]*s[1])


### FIXED CODE ###

a,b = (int(x) for x in input().split())
print(a*b)
N=int(input())
for t in range(N//2):
    if t**2<=N:
        i=t**2
    else:
        break
print(i)

### FIXED CODE ###

N=int(input())
print(int(N**(1/2))**2)
# ABC138D

import sys
sys.setrecursionlimit(1000000000000)
def dfs(kol,adj,v,p):
    for nv in adj[v]:
        if nv==p:
            continue
        else:
            dfs(kol,adj,nv,v)
    kol[v]+=[v]
    if p!=-1:
        kol[p]+=kol[v]
N,Q=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    adj[a-1]+=[b-1]
    adj[b-1]+=[a-1]
    
ct=[0]*N
kol=[[] for i in range(N)]

dfs(kol,adj,0,-1)

for i in range(Q):
    p,x=map(int,input().split())
    for j in kol[p-1]:
        ct[j]+=x

print(ct[0], end="")
for i in range(1,N):
    print(" {}".format(ct[i]),end="")
print("")

### FIXED CODE ###

# ABC138D

import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000000)

def dfs(adj,v,p,px,x,ct):
    x+=px[v]
    for nv in adj[v]:
        if nv==p:
            continue
        else:
            dfs(adj,nv,v,px,x,ct)
    ct[v]+=x

def main():
    N,Q=map(int,input().split())
    adj=[[] for i in range(N)]
    for i in range(N-1):
        a,b=map(int,input().split())
        adj[a-1]+=[b-1]
        adj[b-1]+=[a-1]
    px=[0]*N
    for i in range(Q):
        p,x=map(int,input().split())
        px[p-1]+=x
        
    ct=[0]*N
    dfs(adj,0,-1,px,0,ct)
    
    
    print(ct[0], end="")
    for i in range(1,N):
        print(" {}".format(ct[i]),end="")
    print("")
    
if __name__=="__main__":
    main()
data = input().spilt()

k = int(data[0])
x = int(data[1])

if x <= 500 * k:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

data = input().split()
k = int(data[0])
x = int(data[1])
 
if k * 500 >= x:
  print("Yes")
else:
  print("No")
while 1:
    a = int(input())
    if a ==0:
    break
    a = str(a)
    print([a[i] for i in range(len(a))])
    
    


### FIXED CODE ###

while 1:
    n = input()
    if n == '0':
        break
    print(sum(int(x) for x in n))
import numpy as np
H, W = map(int, input().split())
maze = np.array([[c == '#' for c in input()] for _ in range(H)], dtype=bool)

n_walls = np.sum(maze)
n_aisle = W * H - n_walls

d = dict(enumerate(map(dict, map(enumerate, maze))))
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
adj = {(i, j): {(i + k, j + l): 1 for k, l in directions if not d.get(i + k, {}).get(j + l, True)}
       for i in range(H) for j in range(W) if not d[i][j]}
start = (0, 0)
end = (H-1, W-1)
for i in adj.keys():
    for j in adj.keys():
        for k in adj.keys():
            distance = adj.get(i, {}).get(k, np.inf) + adj.get(k, {}).get(j, np.inf)
            if adj.get(i, {}).get(j, np.inf) > distance:
                adj[i][j] = distance
if np.isinf(adj[start][end]):
    print(-1)
else:
    print(n_aisle - adj[start][end] - 1)

### FIXED CODE ###

H, W = map(int, input().split())
maze = []
distances = []
n_aisle = 0
for i in range(H):
    row = input()
    maze.append(row)
    distances.append([100000000 for i in range(W)])
    n_aisle += row.count('.')

distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

visited = [(0, 0)]
queue = [(0, 0)]
while len(queue) > 0:
    y, x = queue.pop(0)
    for dy, dx in directions:
        y2, x2 = y + dy, x + dx
        if y2 < 0 or y2 >= H or x2 < 0 or x2 >= W:
            continue
        if (y2, x2) in visited:
            continue
        if maze[y2][x2] == '.':
            distances[y2][x2] = distances[y][x] + 1
            visited.append((y2, x2))
            queue.append((y2, x2))

if distances[H - 1][W - 1] == 100000000:
    print(-1)
else:
    print(n_aisle - distances[H - 1][W - 1] - 1)
N = int((input())

if N % 2 == 0:
  print(N // 2)
else:
  print((N // 2) + 1)

### FIXED CODE ###

UNKO = int(input())
print(UNKO // 2 + UNKO % 2)
def main():
    n = int(input())
    s = [input() for _ in range(n)]
    d = []
    ans = 0
    for ss in s:
        c = collections.Counter(ss)
        d.append(c)
    for i in range(n):
        for j in range(i + 1, n):
            if d[i] == d[j]:
                ans += 1              
    print(ans)  
        
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def main():
    n = int(input())
    d = {}
    ans = 0
    
    for _ in range(n):
        ss = ''.join(sorted(input()))
        d[ss] = d.get(ss, 0) + 1
        
    for k, v in d.items():
        if v != 1:
            ans += combinations_count(v, 2)
         
    print(ans)
       
    
if __name__ == '__main__':
    main()
import bisect
import heapq
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

# (d, x, x のインデックス) のリスト
lows = []
highs = []

for xi, [s, t, x] in enumerate(STX):
    # [lo, hi) に出発した人は x で止まる
    lo = bisect.bisect_left(D, s - x)
    hi = bisect.bisect_left(D, t - x)
    lows.append((D[lo], x, xi))
    highs.append((D[hi], x, xi))

lows.sort()
highs.sort()
L = 0
r = 0
# (x, D のインデックス)
heap = []
used = [False for _ in range(len(lows))]

for i, d in enumerate(D):
    while L < len(lows) and lows[L][0] <= d:
        heapq.heappush(heap, (lows[L][1], lows[L][2]))
        L += 1
    while r < len(highs) and highs[r][0] <= d:
        used[highs[r][2]] = True
        r += 1
    while heap and used[heap[0][1]]:
        heapq.heappop(heap)
    if heap:
        print(heap[0][0])
    else:
        print(-1)


### FIXED CODE ###

import bisect
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, Q = list(map(int, next(sys.stdin).split()))
STX = [list(map(int, next(sys.stdin).split())) for _ in range(N)]
D = [int(next(sys.stdin)) for _ in range(Q)]

ans = [-1 for _ in range(Q)]
nexts = [-1 for _ in range(Q)]

for s, t, x in sorted(STX, key=lambda stx: (stx[2], stx[1])):
    # [lo, hi) に出発した人は x で止まる
    # x の小さい順にソート済みなのでここで確定
    lo = max(0, bisect.bisect_left(D, s - x))
    hi = min(len(D), bisect.bisect_left(D, t - x))

    p = lo
    while p < hi:
        if nexts[p] == -1:
            ans[p] = x
            nexts[p] = hi
            p += 1
        else:
            prev = p
            p = nexts[p]
            nexts[prev] = hi

for a in ans:
    print(int(a))
import sys


N, his = sys.stdin.readlines()
N = int(N)
his = [int(hi) for hi in his.split(' ')]
his.append(100000)

cache = {}

def cost(frm):
    if frm == N - 1:
        return 0
    elif frm < N:
        c = cache.get(frm, None)
        if c:
            return c
        c = min(
            cost(frm + 1) + abs(his[frm] - his[frm + 1]),
            cost(frm + 2) + abs(his[frm] - his[frm + 2])
        )
        cache[frm] = c
        return c
    else:
        return 1000000

print(cost(0))

### FIXED CODE ###

import sys

N = int(sys.stdin.readline())
h = [int(hi) for hi in sys.stdin.readline().split(' ')]

dp = [1000000 * N] * N
dp[0] = 0

for i in range(N - 1):
    dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]))
    if i < N - 2:
        dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]))

print(dp[-1])
def read():
    N = int(input().strip())
    L = map(int, input().strip().split())
    return N, L


def solve(N, L):
    L = sorted(L)
    return "Yes" if L[-1] < sum(L[:-1]) else "No"


if __name__ == '__main__':
    inputs = read()
    print("%f" % solve(*inputs))


### FIXED CODE ###

def read():
    N = int(input().strip())
    L = map(int, input().strip().split())
    return N, L


def solve(N, L):
    L = sorted(L)
    return "Yes" if L[-1] < sum(L[:-1]) else "No"


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))
from math import gcd

k = int(input())
ans = 0

n = list(product([i for i in range(1,k+1)],repeat=3))
for a,b,c in n:
    n = gcd(a,b)
    ans += gcd(n,c)
print(ans)


### FIXED CODE ###

from math import gcd

k = int(input())
ans = 0

for a in range(1,k+1):
    for b in range(1,k+1):
        n = gcd(a,b)
        for c in range(1,k+1):
            ans += gcd(n,c)
print(ans)
N,K=[int(i) for i in input().split()]
X=[int(i) for i in input().split()]
m=10**5
for i in range(n-k+1):
    m=min(m,x[k-1+i]-x[i]+min(abs(x[k-1+i]),abs(x[i])))

print(m)

### FIXED CODE ###

N,K=[int(i) for i in input().split()]
X=[int(i) for i in input().split()]
m=10**9
for i in range(N-K+1):
    m=min(m,X[K-1+i]-X[i]+min(abs(X[K-1+i]),abs(X[i])))

print(m)
from collections import Counter
n = int(input().strip())
vs = [int(i) for i in input().split(' ')]
vs1 = vs[::2]
vs2 = vs[1::2]
a = Counter(vs1).most_common()
b = Counter(vs2).most_common()

if a[0][0] != b[0][0]:
    print(n - a[0][1] - b[0][1])
else:
    candidates = []
#    candidates.append(len(vs2))
    if len(a) != 1:
        candidates.append(n - a[1][1] - b[0][1])
    if len(b) != 1:
        candidates.append(n - a[0][1] - b[1][1])
    print(min(candidates))


### FIXED CODE ###

from collections import Counter
n = int(input().strip())
vs = [int(i) for i in input().split(' ')]
vs1 = vs[::2]
vs2 = vs[1::2]
a = Counter(vs1).most_common()
b = Counter(vs2).most_common()

if a[0][0] != b[0][0]:
    print(n - a[0][1] - b[0][1])
else:
    candidates = []
    if len(a) != 1:
        candidates.append(n - a[1][1] - b[0][1])
    if len(b) != 1:
        candidates.append(n - a[0][1] - b[1][1])
    if len(candidates) != 0:
        print(min(candidates))
    else:
        print(n//2)
N, K, L = map(int, input().split())
city = [1 for i in range(N)]
setA = set()
setB = set()
for i in range(K):
    X = set(int(x)-1 for x in input().split())
    for A in setA:
        if A & X != set():
            A = A | X
    else:
        setA.add(X)
for i in range(L):
    Y = set(int(y)-1 for y in input().split())
    for B in setB:
        if B & Y != set():
            B = B | Y
    else:
        setB.add(Y)
for A in setA:
    for B in setB:
        for i in A & B:
            city[i] = len(A&B)
for i in range(N):
    print(city[i], end=" ")

### FIXED CODE ###

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

def fp(x, parentList): #findParent
    if parentList[x] == x:
        return x
    else:
        parentList[x] = fp(parentList[x], parentList)
        return parentList[x]

#各ノードのparentをリストで表現(連結前は自身がparent)
road = [i for i in range(N)]
rail = [i for i in range(N)]

for _ in range(K):
    p, q = map(int, input().split())
    par_p, par_q = fp(p-1, road), fp(q-1, road) #p, qのparent 
    #連結する際、若い番号をparentとする
    if par_p < par_q:
        road[par_q] = par_p
    else:
        road[par_p] = par_q

#railについても同様
for _ in range(L):
    s, t = map(int, input().split())
    par_s, par_t = fp(s-1, rail), fp(t-1, rail)
    if par_s < par_t:
        rail[par_t] = par_s
    else:
        rail[par_s] = par_t

#連結成分の要素をカウント
cnt = {}
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    if key in cnt:
        cnt[key] += 1
    else:
        cnt[key] = 1
#出力
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    ans = cnt[key]
    print(ans, end=" ")
import sys

n, m = list(map(int, input().split()))
ar = [list(map(int, input().split())) for _ in range(m)]
ans = [0 for _ in range(n)]

for a in ar:
    if ans[a[0] - 1] != 0 and ans[a[0] - 1] != a[1]:
        print(-1)
        sys.exit()
    ans[a[0] - 1] = a[1]

if ans[0] == 0:
    if ans[1] == 0:
        ans[1] = 1
    ans[0] = 1

ans = int("".join(map(str, ans)))
print(ans)

### FIXED CODE ###

import math

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

ans = list([0 for _ in range(n)])

err = False
for i in range(m):
    s, c = map(int, input().split(" "))
    if s == 1 and c == 0:
        if n == 1:
            print(0)
            exit()
        err = True
    elif ans[s - 1] == 0:
        ans[s - 1] = c
    elif not ans[s - 1] == c:
        err = True

if ans[0] == 0:
    ans[0] = 1

if (n == 1 and ans[0] == 0) or (n == 1 and m == 0):
    print(0)
    exit()

if err:
    print(-1)
    exit()

print("".join(map(str, ans)))
import numpy as np
lst = list(input().split())

num = len(lst)

A = lst[0] + lst[1]
B = lst[1] + lst[2]
C = lst[0] + lst[2]

print(np.min([A,B,C]))

### FIXED CODE ###

p,q,r = map(int,input().split())    
lst = [p,q,r]

A = lst[0] + lst[1]
B = lst[1] + lst[2]
C = lst[0] + lst[2]

print(min([A,B,C]))
"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
def main():
    import sys
    sys.setrecursionlimit(20000000)
    input = sys.stdin.readline
    N = int(input())
    AB = [{}for _ in range(N+1)]
    for i in range(N-1):
        a,b,c = map(int,input().split())
        AB[a][b] = c
        AB[b][a] = c

    Q,K = map(int,input().split())

    path = {K:""}
    dp = [0]*(N+1)
    def dfs(n,cost):
        path[n]=""
        dp[n]=cost
        for i,c in AB[n].items():
            if i not in path:
                nextcost = (cost+c)%mod
                dfs(i,nextcost)
    dfs(K,0)
    for i in range(Q):
        x,y=map(int,input().split())
        print(dp[x]+dp[y])
main()

### FIXED CODE ###

"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(20000000)
    input = sys.stdin.readline
    N = int(input())
    AB = [[]for _ in range(N+1)]
    for i in range(N-1):
        a,b,c = map(int,input().split())
        AB[a].append((b,c))
        AB[b].append((a,c))

    Q,K = map(int,input().split())

    path = {K:""}
    dp = [0]*(N+1)
    que = deque()
    for n,c in AB[K]:
        que.append((n,c))
    while que:
        now,cost = que.pop()
        path[now]=""
        dp[now]=cost
        for n,c in AB[now]:
            if n not in path:
                que.append((n,cost+c))
    for i in range(Q):
        x,y=map(int,input().split())
        print(dp[x]+dp[y])
main()