Harryxun/stf_run huggingface dataset:
a, b = map(int, input().split())
s = a*b
if s % 2 == 0:
  print("Even")
  else
  print("Odd")

### FIXED CODE ###

a, b = map(int, input().split())
s = a*b
if s % 2 == 0:
  print("Even")
else:
  print("Odd")
H,W=map(int,input().split())
a=[list(map(int,input().split())) for _ in[0]*H]
res=[]
for i in range(H):
    for j in range(W-1):
        if a[i][j]%2==1:
            a[i][j]-=1
            a[i][j+1]+=1
            res.append([i,j,i,j+1])
for i in range(H-1):
    if a[i][-1]%2==1:
        a[i][-1]-=1
        a[i+1][-1]+=1
        res.append([i,j,i+1,j])
print(len(res))
for a,b,c,d in res:
    print(a+1,b+1,c+1,d+1)

### FIXED CODE ###

H,W=map(int,input().split())
a=[list(map(int,input().split())) for _ in[0]*H]
res=[]
for i in range(H):
    for j in range(W-1):
        if a[i][j]%2==1:
            a[i][j]-=1
            a[i][j+1]+=1
            res.append([i,j,i,j+1])
for i in range(H-1):
    if a[i][-1]%2==1:
        a[i][-1]-=1
        a[i+1][-1]+=1
        res.append([i,W-1,i+1,W-1])
print(len(res))
for a,b,c,d in res:
    print(a+1,b+1,c+1,d+1)
def dfs(n):
    if n == 0:return 0
    return dfs(n % format(n, "b").count("1")) + 1
n = int(input())
x = input()
c = x.count("1")
a = int(x, 2)
j, k = a % (c + 1), a % (c - 1)
if c == 1:
    for i in range(n):
        if x[i] == "1":
            print(0)
        elif i == n - 1:
            print(2)
        else:
            print(1)
else:
    for i in range(n):
        if x[i] == "1":print(dfs((k - pow(2, n - i - 1, c - 1)) % (c - 1)) + 1)
        else:print(dfs((j + pow(2, n - i - 1, c + 1)) % (c + 1)) + 1)

### FIXED CODE ###

def dfs(n):
    if n == 0:return 0
    return dfs(n % format(n, "b").count("1")) + 1
n = int(input())
x = input()
c = x.count("1")
a = int(x, 2)
if c == 1:
    for i in range(n):
        if x[i] == "1":
            print(0)
        elif i == n - 1:
            print(2)
        else:
            print(1)
else:
    j, k = a % (c + 1), a % (c - 1)
    for i in range(n):
        if x[i] == "1":print(dfs((k - pow(2, n - i - 1, c - 1)) % (c - 1)) + 1)
        else:print(dfs((j + pow(2, n - i - 1, c + 1)) % (c + 1)) + 1)
n,k = map(int,input().split(" "))
s = list(input())

a = [0]
tmp = 1
for i in range(n-1):
    if s[i] == s[i+1]:
        tmp += 1
    else:
        a.append(tmp)
        tmp += 1
a.append(tmp)
m = len(a)
ans = 1
if len(a) == 2 or m-2*k < 1:
    ans = a[m-1]
elif s[0] == "1":
    for i in range(1,m-2*k+1):
        if i % 2 != 0:        
            ans = max(ans,a[2*k+i]-a[i-1])
        else:
            ans = max(ans,a[2*k+i-1]-a[i-1])
else:
    for i in range(1,m-2*k):
        if i % 2 == 0:        
            ans = max(ans,a[2*k+i]-a[i-1])
        else:
            ans = max(ans,a[2*k+i-1]-a[i-1])

print(ans)


### FIXED CODE ###

n,k = map(int,input().split(" "))
s = list(input())
a = [1]
for i in range(1,n):
    if s[i] != s[i-1]:
        a.append(i+1)
m = len(a)
ans = 1
i = 1
for i in range(m):
    if s[a[i]-1] == "1":
        if 2*k + i +1 < m:        
            ans = max(ans,a[2*k+i+1]-a[i])
        else:
            ans = max(ans,n+1- a[i])
    else:
        if 2*k+i< m:        
            ans = max(ans,a[2*k+i]-a[i])
        else:
            ans = max(ans,n+1-a[i])
print(ans)
N, x = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = 0

def need_to_eat(a, i):
    return a[i] + a[i+1] > x


for i in range(N-1):
    while need_to_eat(a, i):
        a[i] -= 1
        ans += 1

print(ans)


### FIXED CODE ###


s = input().split()
output = ''

for s_i in s:
    output += s_i[0]

print(output)
def is_collided(x: int, y: int, xn: list, ym: list) -> bool:
    xn_max = max(xn)
    ym_min = min(ym)

    if xn_max > ym_min:
        return True
    # xn_max ~ ym_minとx ~ yが重なっていれば衝突しない
    if xn_max < x < ym_min or xn_max < y <= ym_min or \
    x < xn_max < y or x < x < ym_min <= y:
        return False
    return True


def main():
    line1: list = list( map(lambda x:int(x), input().split(' ')) )
    line2: list = list( map(lambda x:int(x), input().split(' ')) )
    line3: list = list( map(lambda x:int(x), input().split(' ')) )
    if is_collided(line1[2], line2[3], line2, line3):
        print("War")
    else:
        print("No War")

if __name__=='__main__':
    main()

### FIXED CODE ###

def is_collided(x: int, y: int, xn: list, ym: list) -> bool:
    xn_max = max(xn)
    ym_min = min(ym)

    if xn_max >= ym_min:
        return True
    # xn_max ~ ym_minとx ~ yが重なっていなければ衝突する
    return xn_max >= y or ym_min <= x

def main():
    line1 = list( map(lambda x:int(x), input().split(' ')) )
    line2 = list( map(lambda x:int(x), input().split(' ')) )
    line3 = list( map(lambda x:int(x), input().split(' ')) )
    print("War") if is_collided(line1[2], line1[3], line2, line3) else  print("No War")

if __name__=='__main__':
    main()
import copy
from sys import exit
n, k = map(int, input().split())
A = list(map(int, input().split()))

mod = 10**9 + 7

plus = []
minus = []
for a in A:
    if a >= 0:
        plus.append(a)
    else:
        minus.append(a)
plus.sort()
minus.sort(reverse=True)

def is_ans_plus():
    if len(plus) > 0:
        if n == k:
            if len(minus) % 2 == 0:
                return True
            else:
                return  False
        else:
            return True
    else:
        if k % 2 == 0:
            return True
        else:
            return False

ans = 1
if is_ans_plus():
    if k % 2 == 1:
        ans *= plus.pop()
        k -= 1
    for i in range(k // 2):
        plus_pair, minus_pair = -1, -1
        if len(plus) >= 2:
            plus_pair = plus[-1] * plus[-2]
        if len(minus) >= 2:
            minus_pair = minus[-1] * minus[-2]
        if plus_pair >= minus_pair:
            ans *= plus_pair
            plus.pop()
            plus.pop()
        else:
            ans *= minus_pair
            minus.pop()
            minus.pop()
        ans %= mod
else:
    ans = 1
    for i in range(k):
        ans *= minus[i]
        ans %= mod
print(ans)


### FIXED CODE ###

import copy
from sys import exit
n, k = map(int, input().split())
A = list(map(int, input().split()))

mod = 10**9 + 7

plus = []
minus = []
for a in A:
    if a >= 0:
        plus.append(a)
    else:
        minus.append(a)
plus.sort()
minus.sort(reverse=True)

def is_ans_plus():
    if len(plus) > 0:
        if n == k:
            if len(minus) % 2 == 0:
                return True
            else:
                return  False
        else:
            return True
    else:
        if k % 2 == 0:
            return True
        else:
            return False

ans = 1
if is_ans_plus():
    if k % 2 == 1:
        ans *= plus.pop()
        k -= 1
    for i in range(k // 2):
        plus_pair, minus_pair = -1, -1
        if len(plus) >= 2:
            plus_pair = plus[-1] * plus[-2]
        if len(minus) >= 2:
            minus_pair = minus[-1] * minus[-2]
        if plus_pair >= minus_pair:
            ans *= plus_pair
            plus.pop()
            plus.pop()
        else:
            ans *= minus_pair
            minus.pop()
            minus.pop()
        ans %= mod
else:
    ans = -1
    A = sorted([abs(a) for a in A])
    for i in range(k):
        ans *= A[i]
        ans %= mod
print(ans)
(d, g), *s = [list(map(int, i.split())) for i in open(0)]
s = [[i[0] * -~n * 100 + i[1], i[0]] for n, i in enumerate(s)]
a = 10**9
for b in range(1 << d):
    su = sum(s[i][0] * (b >> i & 1) for i in range(d))
    n = sum(s[i][1] * (b >> i & 1) for i in range(d))
    if su <= g:
        m = d-bin(b)[2:].zfill(d).find("0")
        if m==-1:
            if su==g:
              print(n)
              exit()
            continue
        e =-~(g-su)//(m*100)
        if e < s[m-1][1]:
            a = min(a,n + e)
    if su > g:
        a = min(a,n)
print(a)

### FIXED CODE ###

(d, g), *s = [list(map(int, i.split())) for i in open(0)]
def c(i,t,l):
    if i==d:
        if t>=g:
            return sum(l)
        else:
            m=d-l[::-1].index(0)
            e = (t - g) // (m * 100)
            if -e < s[m-1][0]:
                return sum(l)-e
            else:
                return 10**3
    return min(c(i+1,t,l+[0]),c(i+1,t+s[i][0]*-~i*100+s[i][1],l+[s[i][0]]))
print(c(0,0,[]))
s=input()

d=[0]*2019
dp=0
d[0]+=1
l=len(s)

for i in range(l-1,-1,-1):
	dp = (dp+int(s[i])*(10**(l-1-i)))%2019
	d[dp]+=1
res=0

for a in d:
	res+=a*(a-1)//2
	
print(res)

### FIXED CODE ###

s,w=map(int,input().split())
print("safe") if s>w else print("unsafe")
for x in range(200):
    print(len(str(sum(list(map(int, input().split()))))))



### FIXED CODE ###

while True:
    try:
        print(len(str(sum(list(map(int, input().split()))))))
    except EOFError:
        break
N,P=map(int,input().split())
S=str(input())
S=S[::-1]
Si=[]
count=0
sum=0
if P==2:
    for i in range(N):
        if int(S[i])%2==0:
            count+=N-i
elif P==5:
    for i in range(N):
        if S[i]=="0" or S[i]=="5":
            count+=N-i
else:
    listS=[int(i) for i in S]
    mod=[(k*10**j)%P for j,k in enumerate(listS)]
    for m in mod:
        sum+=m
        Si.append(sum%P)
        
    for start in range(N):
        if Si[start]==0:
            count+=1            
        for end in range(start+1,N):
            if Si[start]==Si[end]:
                count+=1
print(count)

### FIXED CODE ###

import re
ptr=["A{3}|B{3}"]
str=input()

for valueptr in ptr:
    pattern=re.compile(valueptr)
    res=pattern.search(str)
    if res is None:
        print("Yes")
    else:
        print("No")
n = input()
for i in range(0, n-1):
   R = raw_input().split()
minv = R[0]
maxv = R[1] - R[0]
for j in range(1, n-1):
   maxv = max(maxv, R[j] - minv) 
   minv = min(minv, R[j])
print maxv - minv

### FIXED CODE ###

n = input()
R = []
for i in range(0, n):
   R.append(int(raw_input()))

maxv = R[1] - R[0]
minv = R[0]

for v in range(1, n):
   if minv > R[v]:
      minv = R[v]
   elif maxv < R[v] - minv:
      maxv = R[v] - minv
print maxv
print("YES"if input().count(7)==1else"NO")

### FIXED CODE ###

a,b,c=map(int,input().split());print("YNEOS"[a+b+c!=17or a^b^c!=7::2])
s=int(input())
if int(s[5:7])>4:
  print("TBD")
else:
  print("Heisei")

### FIXED CODE ###

s=input()
if int(s[5:7])>4:
  print("TBD")
else:
  print("Heisei")
S = input()

S[3]="8"

print(S)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jun 19 03:01:30 2018

@author: ashida
"""

S = list(input())

S[3]="8"

print("".join(S))
def main ():
    N = int(input())
    A = list(map(int,input().split()))
    if 0 in A: 
        print (0)
        return
    prod = 1 
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
        print(-1) 
        return
    print(prod) 
main ()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    if 0 in A: 
        print (0)
        return
    prod = 1 
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1) 
            return
    print(prod) 

main()
#! coding: UTF-8
data1 = list(map(int,input().split(" ")))
N = data1[0]
A = data1[1]
B = data1[2]
data2 = list(map(int,input().split(" ")))
data2.sort(reverse=True)
max_avr = 0
for i in range(A):
	max_avr += data2[i]
max_avr /= A
a_num = 0
a_pos = 0
for i in range(N):
	if data2[i] == data2[A-1]:
		a_num += 1
		if i < A:
			a_pos += 1
#確率統計nCr
import math
def nCr(n,r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)
cnt = 0
if a_pos == A:
    while a_pos <= B:
        cnt += nCr(a_num,a_pos)
        a_pos += 1
else:
    cnt += nCr(a_num,a_pos)
print("{0:.6f}".format(max_avr))
print(int(cnt))


### FIXED CODE ###

#! coding: UTF-8
N,A,B = list(map(int,input().split(" ")))
V = list(map(int,input().split(" ")))
V.sort(reverse=True)
max_avr = sum(V[:A]) / A
a_num = V.count(V[A-1])
a_pos = V[:A].count(V[A-1])

#確率統計nCr
import math
def nCr(n,r):
    f = math.factorial
    return f(n) // f(r) // f(n-r)

if V[0] == V[A-1]:
    cnt = sum(nCr(a_num,i) for i in range(A,min(B,a_num)+1)) 
else:
    cnt = nCr(a_num,a_pos)
print("{0:.10f}".format(max_avr))
print(int(cnt))
# -*- coding:utf-8 -*-
import sys
def dfs(x, y, sym):
	tile[x][y] = "."
	for i in range(len(DX)):
		nx = x + DX[i]
		ny = y + DY[i]
		if (0<=nx and nx<N and 0<=ny and ny<M and tile[nx][ny] is sym):
			dfs(nx, ny, sym)

def solve():
	res = 0
	for i in range(N):
		for j in range(M):
			sym = tile[i][j]
			if tile[i][j] != ".":
				if tile[i][j] is sym:
					dfs(i, j, sym)
					res += 1
	print(res)

counter=0
DX = [-1,0,1,0]
DY = [0,-1,0,1]
sys.setrecursionlimit(10**7)
while True:
	line = input()
	if " " in line:
		nums = line.split(" ")
		N = int(nums[0])
		M = int(nums[1])
		tile = [[0 for i in range(N)] for j in range(M)]
	else:
		tile[counter-1] = list(line)
	if N is 0 and M is 0:
		break
	counter += 1
	if counter-1 is M:
		solve()
		counter = 0

### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys
def dfs(x, y, sym):
	tile[x][y] = "."
	for i in range(len(DX)):
		nx = x + DX[i]
		ny = y + DY[i]
		if (0<=nx and nx<N and 0<=ny and ny<M and tile[nx][ny] is sym):
			dfs(nx, ny, sym)

def solve():
	res = 0
	for i in range(N):
		for j in range(M):
			sym = tile[i][j]
			if tile[i][j] != ".":
				if tile[i][j] is sym:
					dfs(i, j, sym)
					res += 1
	print(res)

counter=0
DX = [-1,0,1,0]
DY = [0,-1,0,1]
sys.setrecursionlimit(10**7)
while True:
	line = input()
	if " " in line:
		nums = line.split(" ")
		N = int(nums[0])
		M = int(nums[1])
		tile = [[0 for i in range(M)] for j in range(N)]
	else:
		tile[counter-1] = list(line)
	if N is 0 and M is 0:
		break
	counter += 1
	if counter-1 is N:
		solve()
		counter = 0
import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(m)]
g=nx.Graph()
g.add_edges_from(s)
 
#各部屋の通じてる部屋番のリストを作る
l=[[] for _ in range(n)]
for i in range(m):
    a,b=s[i][0],s[i][1]
    l[a-1].append(b)
    l[b-1].append(a)
#深さのリストを作る
l1=sum(l, []) #一次元化
l1.insert(0,1)
l_depth=list(dict.fromkeys(l1))#深さのリスト
 
# スタート地点からゴール地点までのすべての単純路 (同じ頂点を通らないパス)
k=list(nx.all_simple_paths(g, source=1, target=l_depth[-1]))
 
c=0
ma=0
for i in range(len(k)):
    if len(k[i])>ma:
        ma=len(k[i])
        c-=c+1
    if len(k[i])==ma:
        c+=1
print(c)

### FIXED CODE ###

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

#各部屋の通じてる部屋番のリストを作る
l=[[] for _ in range(n)]
for i in range(m):
    a,b=s[i][0],s[i][1]
    l[a-1].append(b)
    l[b-1].append(a)

def dfs(now, prev, visited):
    visited.append(now)#行った頂点を追加していって全て行ったなら+1
    if len(visited) == n:
        return 1
 
    ret = 0 #条件を満たす数の初期値
    for edge in l[now-1]:#今の場所からいける頂点がまだ行ったことのない場合そこを同様に再度探索
        if edge == prev:
            continue
        if edge in visited:
            continue
 
        ret += dfs(edge, prev, visited[:])#そこで全ての頂点を網羅したなら+1(dfs文最初の部分)
 
    return ret #総計値を返す

print(dfs(1, 0, []))
import sys

MOD = 10 ** 9 + 7

def make_table(size=10**6, p=MOD):
    fac = [None] * (size + 1)
    fac[0] = 1
    for i in range(size):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (size + 1)
    ifac[size] = pow(fac[size], p-2, p)
    for i in range(size, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    return fac, ifac

fac, ifac = make_table(10**5)

def comb(n, r, mod=MOD):
    if r > n or r < 0:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

n, *c = map(int, sys.stdin.read().split())

def main():
    c.sort()
    res = 0
    for i in range(n):
        cnt = 0
        for d in range(1, n+1):
            for j in range(d):
                cnt += comb(i, j) * comb(n-i-1, d-j-1) * (d - j) % MOD
        
        res += c[i] * cnt
        res %= MOD
    return res * 2 ** n % MOD

if __name__ == '__main__':
    ans = main()
    print(ans)

### FIXED CODE ###

import sys

MOD = 10 ** 9 + 7

def make_table(size=10**6, p=MOD):
    fac = [None] * (size + 1)
    fac[0] = 1
    for i in range(size):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (size + 1)
    ifac[size] = pow(fac[size], p-2, p)
    for i in range(size, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    return fac, ifac

fac, ifac = make_table(2*10**5)

def comb(n, r, mod=MOD):
    if r > n or r < 0:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

n, *c = map(int, sys.stdin.read().split())

def main():
    c.sort(reverse=True)
    res = 0
    # for i in range(n):
    #     cnt = 0
    #     for d in range(1, n+1):
    #         for j in range(d):
    #             cnt += comb(i, j) * comb(n-i-1, d-j-1) * (d - j) % MOD
        
    #     res += c[i] * cnt
    #     res %= MOD
    for i in range(n):
        res += c[i] * (i + 2)
        res %= MOD
    return res * 4 ** (n - 1) % MOD

if __name__ == '__main__':
    ans = main()
    print(ans)
s, t = input().split()
a, b = int(input().split())
u = input()

if s == u:
  a = a - 1
else:
  b =  b - 1
  
print("{} {}".format(a, b))

### FIXED CODE ###

s, t = input().split()
a, b = map(int, input().split())
u = input()
 
if s == u:
  a = a - 1
else:
  b =  b - 1
  
print("{} {}".format(a, b))
from collections import deque
s = input()
Q = int(input())
t = []
f = []
c = []
for i in range(Q):
    in_ = list(input().split())
    if in_[0] == "1":
        t.append(1)
        f.append(0)
        c.append(0)
    else:
        t.append(2)
        f.append(int(in_[1]))
        c.append(in_[2])
acc = [0 for _ in range(Q)]
if t[-1] == 1:  acc[-1] = 1
for i in reversed(range(Q - 1)):
    if t[i] == 1:
        acc[i] = acc[i + 1] + 1
    else:
        acc[i] = acc[i + 1]
        
if acc[0] % 2 == 0:
    ans = deque(S)
else:
    ans = deque(S[::-1])
    
for i in range(Q):
    if t[i] == 2:
        if (f[i] + acc[i]) % 2 == 1:
            ans.appendleft(c[i])
        else:
            ans.append(c[i])
print("".join(ans))

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
t = []
f = []
c = []
for i in range(Q):
    in_ = list(input().split())
    if in_[0] == "1":
        t.append(1)
        f.append(0)
        c.append(0)
    else:
        t.append(2)
        f.append(int(in_[1]))
        c.append(in_[2])
acc = [0 for _ in range(Q)]
if t[-1] == 1:  acc[-1] = 1
for i in reversed(range(Q - 1)):
    if t[i] == 1:
        acc[i] = acc[i + 1] + 1
    else:
        acc[i] = acc[i + 1]
        
if acc[0] % 2 == 0:
    ans = deque(S)
else:
    ans = deque(S[::-1])
    
for i in range(Q):
    if t[i] == 2:
        if (f[i] + acc[i]) % 2 == 1:
            ans.appendleft(c[i])
        else:
            ans.append(c[i])
print("".join(ans))
N = int(input())
if N == 1:
    raise RuntimeError()

for k in range(2, N + 1):
    sn = k - 1
    if k * sn != 2 * N:
        continue

    print("Yes")
    print(k)
    s = [[0] * sn for _ in range(sn)]
    for i in range(sn):
        s[i][i] = s[i-1][i-1] + (i + 1)
        for j in range(i + 1, sn):
            s[i][j] = s[i][j-1] + j
            s[j][i] = s[i][j]
    s.append([s[i][i] for i in range(sn)])
    for x in s:
        print(sn, " ".join(map(str, x)))
    break
else:
    print("No")

### FIXED CODE ###

N = int(input())
for k in range(1, N + 2):
    sn = k - 1
    if k * sn != 2 * N:
        continue

    print("Yes")
    print(k)
    s = [[0] * sn for _ in range(sn)]
    for i in range(sn):
        s[i][i] = s[i-1][i-1] + (i + 1)
        for j in range(i + 1, sn):
            s[i][j] = s[i][j-1] + j
            s[j][i] = s[i][j]
    s.append([s[i][i] for i in range(sn)])
    for x in s:
        print(sn, " ".join(map(str, x)))
    break
else:
    print("No")
a,b,c,d = map(int,input().split())

print('Yes' if a = b = c or b = c = d else 'No')

### FIXED CODE ###

a,b,c,d = input()

print('Yes' if a == b == c or b == c == d else 'No')
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def WF(mat, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
    return mat


N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    roads[a-1][b-1] = c
    roads[b-1][a-1] = c

roads = WF(roads)
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1
kyuyu = WF(kyuyu)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)


### FIXED CODE ###

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


def WF(mat, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
    return mat


N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    roads[a-1][b-1] = c
    roads[b-1][a-1] = c

roads = WF(roads, N)
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1
kyuyu = WF(kyuyu, N)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)
A,B,C=input().split()

a=int(A)
b=int(B)
c=int(C)

if a>=b:
  if a>=c:
    x=a
    if b>=c:
      y=b
      z=c
      else:
        y=c
        z=b
    else:
      x=c
      y=a
      z=b
else:
  if b>=c:
    x=b
    if a>=c:
      y=a
      z=c
      else:
        y=c
        z=a
    else:
      x=c
      y=b
      z=a

n==x*100+y*10+z
print(n)

### FIXED CODE ###

A,B,C=input().split()

a=int(A)
b=int(B)
c=int(C)

if a>=b:
  if a>=c:
    x=a
    if b>=c:
      y=b
      z=c
    else:
        y=c
        z=b
  else:
      x=c
      y=a
      z=b
else:
  if b>=c:
    x=b
    if a>=c:
      y=a
      z=c
    else:
        y=c
        z=a
  else:
      x=c
      y=b
      z=a

n=x*10+y+z
print(n)
s = input()
x = list()
cnt = 0
for i in range(len(s)):
    if s[i] == "A" or s[i] == "T" or s[i] == "G" or s[i] == "C":
        cnt += 1
    else:
        x.append(cnt)
        cnt = 0
print(max(x))

### FIXED CODE ###

s = input()
x = list()
cnt = 0
for i in range(len(s)):
    if s[i] == "A" or s[i] == "T" or s[i] == "G" or s[i] == "C":
        cnt += 1
        if i == len(s) - 1:
            x.append(cnt)
    else:
        x.append(cnt)
        cnt = 0
print(max(x))
N = int(input())
edge = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    edge[a-1].append((c, b-1))
    edge[b-1].append((c, a-1))
Q, K = map(int, input().split())
query = [tuple(map(int, input().split())) for _ in range(Q)]

import heapq

def dijkstra_heap(s):
    d = [10**12] * N
    used = [False] * N
    d[s] = 0
    used[s] = True
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist, e)
    while len(edgelist):
        min_edge = heapq.heappop(edgelist)
        if used[min_edge[1]]:
            continue
        v = min_edge[1]
        d[v] = min_edge[0]
        used[v] = True
        for e in edge[v]:
            heapq.heappush(edgelist, [e[0] + d[v], e[1]])
    return d

dist = dijkstra_heap(K-1)
for q in query:
    x, y = q[0], q[1]
    x -= 1
    y -= 1
    print(dist[x] + dist[y])

### FIXED CODE ###

N = int(input())
edge = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    edge[a-1].append((c, b-1))
    edge[b-1].append((c, a-1))
Q, K = map(int, input().split())
query = [tuple(map(int, input().split())) for _ in range(Q)]

import heapq

def dijkstra_heap(s):
    d = [10**12] * N
    used = [False] * N
    d[s] = 0
    used[s] = True
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist, e)
    while len(edgelist):
        min_edge = heapq.heappop(edgelist)
        if used[min_edge[1]]:
            continue
        v = min_edge[1]
        d[v] = min_edge[0]
        used[v] = True
        for e in edge[v]:
            heapq.heappush(edgelist, (e[0] + d[v], e[1]))
    return d

dist = dijkstra_heap(K-1)
for q in query:
    x, y = q[0], q[1]
    x -= 1
    y -= 1
    print(dist[x] + dist[y])