Harryxun/stf_run huggingface dataset:
import sys #追加
sys.setrecursionlimit(500*500)
N,K=map(int,input().split())
A=list(map(int,input().split()))
ans=[]
def saiki(B):
    if len(B)==K+1:
        ans.append(B)
        print(B[-1])
        return
    B.append(A[B[-1]-1])
    saiki(B)
saiki([1])
#print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
kari=set()
hako=set()
count=1
cnt=1
zahyo=0
ans=0
kari.add(zahyo)
if K<=10**6:
    for i in range(K):
        ans=A[ans]-1
    print(ans+1)
    exit()
for i in range(N):
    zahyo=A[zahyo]-1
    if zahyo not in kari:
        kari.add(zahyo)
        count+=1
    else:
        break

hako.add(zahyo)
for i in range(N):
    zahyo=A[zahyo]-1
    if zahyo not in hako:
        hako.add(zahyo)
        cnt+=1
    else:
        break
count=len(kari)
cnt=len(hako)
kaisu=K-count
#print(zahyo)
if kaisu>N:
    kaisu=kaisu%cnt
for i in range(kaisu):
    zahyo=A[zahyo]-1
#print(zahyo,kaisu,count,cnt)
#print(kari,hako)
print(zahyo+1)
from collections import Counter

import sys

readline = sys.stdin.buffer.readline

def solver(int N, list A, int Q, list BC):
    d = Counter(A)

    sub_s = sum(A)

    for b, c in BC:
        sub_s += d[b] * (c - b)
        d[c] += d[b]
        d[b] = 0

        print(sub_s)


def run():
    N = int(readline())
    A = list(map(int, readline().split()))

    Q = int(readline())
    BC = [list(map(int, readline().split())) for _ in range(Q)]

    solver(N, A, Q, BC)

run()


### FIXED CODE ###

from collections import Counter

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

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

d = Counter(A)

sub_s = sum(A)

for b, c in BC:
    sub_s += d[b] * (c - b)
    d[c] += d[b]
    d[b] = 0

    print(sub_s)
n,k=map(int,input().split())
p=list(map(int,input().split()))
ans=[]
for i in range(n-k):
  ans.append(sum(p[i:i+k]))
max_value=max(ans)
max_index=ans.index(max_value)
total=0
for i in p[max_index:max_index+k]:
  total+=(i+1)/2
print(total)
          

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
ans=[sum(p[0:k])]
for i in range(1,n-k+1):
  ans.append(ans[i-1]+p[i+k-1]-p[i-1])
max_value=max(ans)
max_index=ans.index(max_value)
total=0
for i in p[max_index:max_index+k]:
  total+=(i+1)/2
print(total)
a,b,c=map(int,input().split())
if a=b=c:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

a,b,c=map(int,input().split())
if a==b==c:
    print('Yes')
else:
    print('No')
n = int(input())
import functools
from functools import reduce

def gcd(numbers):
    return reduce(functools.gcd, numbers)

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

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


num = []
for i in range(n):
    num.append(int(input()))
print(lcm(num))


### FIXED CODE ###

n = int(input())
def gcd(a,b):
    while b != 0:
        a, b = b, a % b
    return a
# 最小公倍数
def lcm(a,b):
    return a // gcd(a,b) * b

ans = 1
for i in range(n):
    t = int(input())
    ans = lcm(ans,t)
print(ans)
S = input();
 
if S[3]==S[4] & S[5]==S[6]:
  print("Yes");
else:
  print("No");

### FIXED CODE ###

S = input();
 
if S[2]==S[3] and S[4]==S[5]:
  print("Yes");
else:
  print("No");
import itertools
import math

n = input()
p = input()
q = input()
i==0
for x in itertools.permutations(range(1,n+1), n):
	i += 1
	if p == x:
      a = i
    elif q == x:
      b = i
print(math.abs(a-b))

### FIXED CODE ###

import itertools
#import math

n = int(input())
#n = 2
#p = tuple(map(int,input().split(" ")))
#q = tuple(map(int,input().split(" ")))

p = input()
q = input()
#print(n)
#print(p)
i = 0
#a = 0 
#b = 0

for x in itertools.permutations(range(1,n+1), n):
	#print(x)
	x = " ".join(map(str,x))
	#print(x)
	i += 1
	if x == p:
		a = i
		#print(i)
	if x == q:
		b = i
		#print(i)

print(abs(a-b))
from fractions import gcd

N, M = list(map(int, input().split()))
S = input()
T = input()

L = (N * M) // gcd(N, M)

L1 = [0]
L2 = [0]

from collections import Counter
c = Counter()

for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t-1)
    c[t-1] += 1

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t-1)
    c[t-1] += 1

common = []
dic = dict()
for k, v in c.items():
    if v == 2:
        common.append(k)
        dic[k] = [None, None]

l1_ind = 0  # N-1まで
l2_ind = 0  # M-1まで
for ci in common:
    for i in range(l1_ind, N):
        if L1[i] == ci:
            dic[ci][0] = i
            l1_ind = i
            break

    for i in range(l2_ind, M):
        if L2[i] == ci:
            dic[ci][1] = i
            l2_ind = i
            break

# print(L1)
# print(L2)
# print(common)
# print(dic)

ans = True
for si, ti in dic.values():
    if S[si] != T[ti]:
        ans = False


if ans:
    print(L)
else:
    print(-1)




### FIXED CODE ###

from fractions import gcd

N, M = list(map(int, input().split()))
S = input()
T = input()

L = (N * M) // gcd(N, M)

L1 = [0]
L2 = [0]

from collections import Counter
c = Counter()

for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t-1)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t-1)


d = {}
for i, li in enumerate(L1):
    d[li] = S[i]

# print(d)

ans = True

for i, li in enumerate(L2):
    if not d.get(li):
        continue
    if d[li] != T[i]:
        ans = False

# print(L1)
# print(L2)
# print(common)
# print(dic)

if ans:
    print(L)
else:
    print(-1)
a = int(input())
if a = 1:
  print(1)
  exit(0)
else:
  ans = a*(a+1)/2 - a
  print(int(ans))

### FIXED CODE ###

a = int(input())
ans = a*(a-1)//2
print(int(ans))
A, B = map(int, input().split())

max_num = max(A, B)
target = list(range(2, max_num + 1))

is_prime = [True] * (max_num + 1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(max_num ** 0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, max_num + 1, i):
        is_prime[j] = False
primes = [i for i in range(max_num + 1) if is_prime[i]]

count = 1
for prime in primes:
    if A % prime == 0 and B % prime == 0:
        count += 1
print(count)

### FIXED CODE ###

def prime_facorize(N):
    res = {1}
    for i in range(2, int(N ** 0.5) + 1):
        while N % i == 0:
            res.add(i)
            N /= i

        if N <= 1:
            break
    if N > 1:
        res.add(N)
    return res


A, B = map(int, input().split())
commons = prime_facorize(A) & prime_facorize(B)
print(len(commons))
import math

def myfactorial(n):
  return math.factorial(n) % 1000000007

def combinations_count(n, r):
    return (myfactorial(n) // (myfactorial(n - r) * myfactorial(r))) % 1000000007

n, k = map(int, input().split())
for i in range(1, k+1):
  print(combinations_count(k-1, i-1) * combinations_count(i+1+(n-k)-(i-1)-1, (n-k)-(i-1)) % 1000000007) 

### FIXED CODE ###

import math

def myfactorial(n):
  return math.factorial(n)

def combinations_count(n, r):
  return (myfactorial(n) // (myfactorial(n - r) * myfactorial(r))) % 1000000007

n, k = map(int, input().split())
for i in range(1, k+1):
  if n-k+1 < i:
    print(0)
  else:
    print(combinations_count(k-1, i-1) * combinations_count(n-k+1, i) % 1000000007)
import math
 
N = int(input())
num_list = [0] + [0] * int(math.sqrt(N))  # 0~N
pn_list = []
for i in range(2, int(math.sqrt(N))+2):
    if num_list[i] == 0:
        pn_list.append(i)
        num_list[i::i] = [1] * len(num_list[i::i])
        
count = 0
for pn in pn_list:
    e = 1
    while N%(pn**e)==0 and N//(pn**e)>=1:
        N //= (pn**e)
        e += 1
        count += 1
if count == 0 and N>1:
    count += 1
print(count)

### FIXED CODE ###

N = int(input())

div_counts = []
for i in range(2, int(N**0.5)+1):
  count = 0
  while N%i == 0:
    count += 1
    N //= i
    if N == 1:
      break
  div_counts.append(count)
  
if N != 1:
  div_counts.append(1)

ans = 0
for count in div_counts:
  for i in range(1, count+1):
    if count >= i:
      ans += 1
      count -= i
print(ans)
class SegmentTree:
    def __init__(self, value, N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                self.node[i] = left_i
            else:
                self.node[i] = right_i

    def set_input(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                new_i = left_i
            else:
                new_i = right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def get_input(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def get_output(self, a=0, b=-1):
        return self.get_input(self.get_output_index(a,b))

    def get_output_index(self,
                         a=0, b=-1,
                         k=0, l=0, r=-1):
        if b < 0:
            b = self.N
        if r < 0:
            r = self.N
        if a <= l and r <= b:
            return self.node[k]
        elif r <= a or b <= l:
            return None
        else:
            left_i = self.get_output_index(a,b,2*k+1,l,(l+r)//2)
            right_i = self.get_output_index(a,b,2*k+2,(l+r)//2,r)
            left_v, right_v = self.get_input(left_i), self.get_input(right_i)
            if left_v is None and right_v is None:
                return None
            elif self.comp(left_v, right_v):
                return left_i
            else:
                return right_i

inpl = lambda: list(map(int,input().split()))

if __name__ == '__main__':
    N, M = inpl()
    A = inpl()
    segt = SegmentTree(A, reverse=True)
    for _ in range(M):
        i = segt.get_output_index()
        v = segt.get_input(i)
        segt.set_input(i, v//2)
    print(sum(segt.value)

### FIXED CODE ###

import heapq
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
A = inpl()
q = []
for a in A:
    heapq.heappush(q,-a)
for _ in range(M):
    a = -heapq.heappop(q)
    a //= 2
    heapq.heappush(q,-a)
print(-sum(q))
import math
import functools
def lcm(x,y):
  return(x*y)//math.gcd(x,y)

n=int(input())
A=list(map(int,input().split()))
num=functools.reduce(lcm,A)
def f(n):
  return sum(list(map(lambda x:n%x,A)))
print(f(num-1))

### FIXED CODE ###

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

m =1
for i in range(len(mods)):
  m *= mods[i]

sums = 0
for i in range(len(mods)):
  sums += (m-1) %mods[i]

print(sums)
N,T,A = map(int,input().split()); INF = float("inf")
T-=1;A-=1 #0index
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 #0index
  G[a].append(b);G[b].append(a)

disT = [INF for _ in range(N)]; disT[T] = 0
disA = [INF for _ in range(N)]; disA[A] = 0

def dfs(v, L):
  for u in G[v]:
    if L[u] != INF:
      continue
    L[u] = L[v]+1
    dfs(u,L)
dfs(T,disT)
dfs(A,disA)
#print(disT)
#print(disA)
ans = 0
for i in range(N):
  if disT[i] < disA[i]:
    ans = max(ans,disA[i]-1)
print(ans)
    

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
N,T,A = map(int,input().split()); INF = float("inf")
T-=1;A-=1 #0index
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 #0index
  G[a].append(b);G[b].append(a)

disT = [INF for _ in range(N)]; disT[T] = 0
disA = [INF for _ in range(N)]; disA[A] = 0

def dfs(v, L):
  for u in G[v]:
    if L[u] != INF:
      continue
    L[u] = L[v]+1
    dfs(u,L)
dfs(T,disT)
dfs(A,disA)
#print(disT)
#print(disA)
ans = 0
for i in range(N):
  if disT[i] < disA[i]:
    ans = max(ans,disA[i]-1)
print(ans)
N,M = map(int,input().split())
XY = [[] for i in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    XY[x-1].append(y-1)

dp = [-1 for i in range(N)]
def search(i):
    if dp[i] != -1:
        return dp[i]
    c = 0
    start = XY[i]
    for s in start:
        c = max(c,search(s)+1)
    dp[i] = c
    return dp[i]

a = 0
for i in range(N):
    a = max(a,search(i))
print(a)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5+10)
input = sys.stdin.readline

N,M = map(int,input().split())
XY = [[] for m in range(N)]
for l in range(M):
    x,y = map(int,input().split())
    XY[x-1].append(y-1)

dp = [-1 for k in range(N)]
def search(i):
    if dp[i] != -1:
        return dp[i]
    c = 0
    start = XY[i]
    for s in start:
        c = max(c,search(s)+1)
    dp[i] = c
    return dp[i]

a = 0
for i in range(N):
    a = max(a,search(i))
print(a)
N = int(input())
H = list(map(int,input().split()))	
bool 
for i in range (1, N):
  if H[i-1] == H[i] or H[i] == H[i-1] + 1:
    True
  elif H[i+1] == H[i] - 1:
    H[i] -= 1
    if H[i-1] > H[i]:
      False
if (True):
  print('Yes' )
else:
  print('No')
  
    
    
  


### FIXED CODE ###

n = int(input())
lis = list(map(int,input().split()))
lis[0]-=1

for i in range(n-1):
  if lis[i] < lis[i+1]:
    lis[i+1] -= 1
  elif lis[i] > lis[i+1]:
    print("No")
    exit()
print("Yes")
while(1):
    [n,m]=map(int,raw_input().split())
    if n==0:    break
    D=[[] for i in range(n+1)]
    D[0]=range(1,n+1)
    nflg=0
    for i in range(m):
        [u,v]=map(int,raw_input().split())
        D[u].append(v)
        D[v].append(u)
        if len(D[u])>2 or len(D[v])>2:
            nflg=1
    if nflg:
        print 'no'
    else:
        bkf=0
        while (len(D[0])>0):
            st=D[0].pop()
            st0=st
            while len(D[st])!=0:
               nxt=D[st].pop()
               if nxt!=st0:
                   D[0].remove(nxt)
                   D[nxt].remove(st)
                   st=nxt
               else:
                   print 'no'
                   bkf=1
                   break
            if bkf:    break
        else:
            print 'yes'
            

### FIXED CODE ###

while(1):
    [n,m]=map(int,raw_input().split())
    if n==0:    break
    D=[[] for i in range(n+1)]
    D[0]=range(1,n+1)
    nflg=0
    for i in range(m):
        [u,v]=map(int,raw_input().split())
        D[u].append(v)
        D[v].append(u)
        if len(D[u])>2 or len(D[v])>2:
            nflg=1
    if nflg:
        print 'no'
    else:
        bkf=0
        while (len(D[0])>0):
            st=D[0].pop()
            if len(D[st])==2:
                D[0].append(st)
            st0=st
            while len(D[st])!=0:
               nxt=D[st].pop()
               if nxt!=st0:
                   D[0].remove(nxt)
                   D[nxt].remove(st)
                   st=nxt
               else:
                   print 'no'
                   bkf=1
                   break
            if bkf:    break
        else:
            print 'yes'
N, A = map(int,input().split())
t=N**2-A
print(t)

### FIXED CODE ###

N = int(input())
A = int(input())
t=N**2-A
print(t)
def together(n , a):

    listans = [0]*(10**5)

    for i in range(n):
        listans[a[i] - 1] += 1
        listans[a[i]] += 1
        listans[a[i] + 1] += 1

    return max(listans)


def main():
    n = int(input())
    a = list(map(int,input().split()))
    print(together(n , a))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def together(n , a):

    listans = [0]*(10**5+2)

    for i in range(n):
        listans[a[i] - 1] += 1
        listans[a[i]] += 1
        listans[a[i] + 1] += 1

    return max(listans)


def main():
    n = int(input())
    a = list(map(int,input().split()))
    print(together(n , a))

if __name__ == '__main__':
    main()
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd,numbers)

N=int(input())
A=[]
A=list(map(int,input().split()))
len=len(A)
gcd=1
new=A[0]

if gcd_list(A)>gcd:
    gcd=gcd_list(A)

if(len>2):
    for i in range(len):
        x=A.pop(i)
        if gcd_list(A)>gcd:
            gcd=gcd_list(A)
            new=gcd
            j=i
        A.insert(i,x)
A.pop(j)
A.insert(j,gcd)
print(gcd)


### FIXED CODE ###

import sys

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

n=int(input())
al=input().split()
al_i = [int(s) for s in al]

if (n == 2):
   print(max(al_i[0],al_i[1]))
   sys.exit()

fg = [0] * n
bg = [0] * n

for x in range(n):
   if (x == 0):
       fg[0] = al_i[0]
       y = 1
   else:
      while y <= x:
         fg[y] = gcd(fg[y-1], al_i[y])
         y += 1

for x in range(n):
   if (x == 0):
      bg[0] = al_i[n-1]
      y = 1
   else:
      while y <= x:
         bg[y] = gcd(bg[y-1], al_i[n-1-y])
         y += 1

m = 0
gm = 0

for x in range(n):
   if (x == 0):
      g = bg[n-2]
   elif (x == n-1):
      g = fg[n-2]
   else:
      g = gcd(fg[x-1],bg[n-2-x])
   if (g > gm):
      gm = g

print(gm)
N = int(input())
result = 0
for i in N:
    if int(i) == 9:
        result += 1
if result >= 1:
    print("Yes")
else:
    print("No")
    

### FIXED CODE ###

N = input()
result = 0
for i in N:
    if int(i) == 9:
        result += 1
if result >= 1:
    print("Yes")
else:
    print("No")
N,K=list(map(int,input().split()))

S = list(input())

S[K] = S[K].lower()

print(''.join(S))


### FIXED CODE ###

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

for i in range(len(S)):
    if i != K-1:
        print(S[i],end='')
    else:
        print(chr(ord(S[i])+32),end="")
from collections import deque
input = sys.stdin.readline

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

if N == 1:
  if S == "1" or K >= 1:
    print(1)
  else:
    print(0)
    
else:
  num = deque([])
  if S[0] == "0":
    num.append(0)
  cnt = 1
  ans = 0
  M = 2 * K + 1
  
  for i in range(1,N):
    if S[i] == S[i - 1]:
      cnt += 1
    else:
      num.append(cnt)
      cnt = 1
      
    if len(num) > M:
      num.popleft()

    if S[i - 1] == "1":
      ans = max(sum(num),ans)
    
    if i == N - 1:
      num.append(cnt)
      if len(num) > M:
        num.popleft()
      if S[i] == "1":
        ans = max(sum(num),ans)
  
  print(ans)

### FIXED CODE ###

from operator import add
from collections import deque
from itertools import accumulate

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

if N == 1:
  if S == "1" or K >= 1:
    print(1)
  else:
    print(0)
    
else:
  num = []
  cnt = 1
  ans = 0
  M = 2 * K + 1

  for i in range(1,N):
    if S[i] == S[i - 1]:
      cnt += 1
    else:
      num.append(cnt)
      cnt = 1
  num.append(cnt)

  if S[0] == "0":
    num = [0] + num
  
  acc = list(accumulate(num,add))
  acc = [0] + acc
  A = len(acc)
  
  for left in range(0,A,2):
    right = min(A - 1,left + M)
    ans = max((acc[right] - acc[left]),ans)
    
  print(ans)
N,K = map(int, input().split())
H = list(map(int, input().split()))
H.sort()
for i in range(K):
    H.pop()
print(sum(H))


### FIXED CODE ###

N,K = map(int, input().split())
H = list(map(int, input().split()))
H.sort()
for i in range(K):
    H.pop()
    if len(H) == 0:
        break
print(sum(H))
input()
l = map(int, raw_input().split())
l.reverse()
print(" ".join(tuple(l)))

### FIXED CODE ###

input()
l = map(int, raw_input().split())
l.reverse()
print(" ".join(map(str, l)))
import numpy as np
a,b,n=map(int,input().split())

x=np.arange(1,n+1)

s1=np.floor(a*x/b)
s2=a*np.floor(x/b)
s=s1-s2
print(int(np.max(s)))

### FIXED CODE ###

a, b, n = list(map(int, input().split()))
x = min(b - 1, n) # b-1がいいけど、上限 nの制約あり
ans = int(a * x / b)
print(ans)
n=int(input())
ans=1
a=list(map(int,input().split()))
m=n-a.count(1)
b=sorted(a)
del b[:a.index(2)-1]
for i in range(n):
    ans*=b[i]
    if 0 in a:
        ans=0
        break
    if m>68:
        ans=-1
        break
    if ans>1000000000000000000:
        ans=-1
        break
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
flag=0
ans=0
if 0 in a:
    flag=1
if flag==0:
    ans=1
    for i in range(n):
        ans*=a[i]
        if ans>1000000000000000000:
            flag=-1
            break
if flag==-1:
    print(-1)
else:
    print(ans)
n = input()

lst = list(map(int, list(n)))
print(sum(lst[0], lst[0] - 1 + 9 * (len(lst) - 1)))


### FIXED CODE ###

n = input()

lst = list(map(int, list(n)))
print(max(sum(lst), lst[0] - 1 + 9 * (len(lst) - 1)))
# http://wakabame.hatenablog.com/entry/2017/09/03/213522
# おまじない
import sys
input = sys.stdin.readline

# ノード数
N = int(input())

# 各要素は(元ノード, 先ノード, コスト)のタプルになっている
edges = [list(map(int, input().split())) for i in range(N)]

# クエリ数と経由ノード
Q, K = map(int, input().split())

# クエリ一覧
xy = [list(map(int, input().split())) for i in range(Q)]


# まず経由地から各ノードのへの距離をメモする
def BFS(K, edges, N):
    # ノード分のリストを持ったリストの定義
    # ノード番号はインデックス-1に対応．つながっている先のノードとそこへのコストのタプルが入る
    roots = [ [] for i in range(N) ]
    for a, b, c in edges:
        roots[a-1] += [(b-1, c)]
        roots[b-1] += [(a-1, c)]
    # memo
    dist = [-1] * N
    # たどり着いたノードのリスト
    stack = []
    stack.append(K)
    dist[K] = 0
    while stack:
        label = stack.pop(-1)
        for i, c roots[label]:
            # 初到達ならmemoしてstackに追加
            # これはグラフが木構造であるから言えること．そうでなければコスト最小値しか採用しては行けない？
            if dist[i] == -1:
                dist[i] = dist[label] + c
                stack += [i]
    return dist

distance = BFS(K - 1, edges, N)

for i in range(Q):
    print(distance[xy[i][0] - 1] + distance[xy[i][1] - 1])
            




### FIXED CODE ###

# http://wakabame.hatenablog.com/entry/2017/09/03/213522
# おまじない
import sys
input = sys.stdin.readline

# ノード数
N = int(input())

# 各要素は(元ノード, 先ノード, コスト)のタプルになっている
edges = [list(map(int, input().split())) for i in range(N - 1)]

# クエリ数と経由ノード
Q, K = map(int, input().split())

# クエリ一覧
xy = [list(map(int, input().split())) for i in range(Q)]


# まず経由地から各ノードのへの距離をメモする
def BFS(K, edges, N):
    # ノード分のリストを持ったリストの定義
    # ノード番号はインデックス-1に対応．つながっている先のノードとそこへのコストのタプルが入る
    roots = [ [] for i in range(N) ]
    for a, b, c in edges:
        roots[a-1] += [(b-1, c)]
        roots[b-1] += [(a-1, c)]
    # memo
    dist = [-1] * N
    # たどり着いたノードのリスト
    stack = []
    stack.append(K)
    dist[K] = 0
    while stack:
        label = stack.pop(-1)
        for i, c in roots[label]:
            # 初到達ならmemoしてstackに追加
            # これはグラフが木構造であるから言えること．そうでなければコスト最小値しか採用しては行けない？
            if dist[i] == -1:
                dist[i] = dist[label] + c
                stack += [i]
    return dist

distance = BFS(K - 1, edges, N)

for i in range(Q):
    print(distance[xy[i][0] - 1] + distance[xy[i][1] - 1])
N, M = [int(x) for x in input().split()]
links = [tuple(map(int, input().split())) for _ in range(M)]
S, T = [int(x) for x in input().split()]

d = {}
for x, y in links:
    if x in d:
        d[x][0].add(y)
    else:
        d[x] = [{y}, False]

def next_node(start):
    history = set()
    for s in start:
        history |= d[s][0]
    return history

history = {S}
s = 1
while True:
    for _ in range(3):
        history = next_node(history)
    if T in history:
        print(s)
        break
    for h in tuple(history):
        if d[h][1]:
            history.remove(h)
        else:
            d[h][1] = True
    if len(history) == 0:
        print(-1)
        break
    s += 1
    

### FIXED CODE ###

N, M = [int(x) for x in input().split()]
links = [tuple(map(int, input().split())) for _ in range(M)]
S, T = [int(x) for x in input().split()]

d = {}
for x, y in links:
    if x in d:
        d[x][0].add(y)
    else:
        d[x] = [{y}, False]

def next_node(start):
    history = set()
    for s in start:
        if s in d:
            history |= d[s][0]
    return history

history = {S}
s = 1
while True:
    for _ in range(3):
        history = next_node(history)
    if T in history:
        print(s)
        break
    for h in tuple(history):
        if h not in d or d[h][1]:
            history.remove(h)
        else:
            d[h][1] = True
    if len(history) == 0:
        print(-1)
        break
    s += 1