Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline

from itertools import accumulate
from operator import add

def solve():
    def getAccAss(Ass):
        accAss = [[0] * (len(Ass[0])+1)] + [accumulate([0] + As) for As in Ass]
        for x in range(1, len(accAss)):
            accAss[x] = list(map(add, accAss[x], accAss[x-1]))
        return accAss
    def getRangeSum2D(accAss, xFr, xTo, yFr, yTo):
        return accAss[xTo+1][yTo+1] - accAss[xTo+1][yFr] - accAss[xFr][yTo+1] + accAss[xFr][yFr]

    N, M, Q = map(int, input().split())
    Ass = [list(map(int, list(input().rstrip()))) for _ in range(N)]

    numXss = [[0]*(M) for _ in range(N-1)]
    for x, (A1s, A2s) in enumerate(zip(Ass, Ass[1:])):
        for y, (A1, A2) in enumerate(zip(A1s, A2s)):
            if A1&A2:
                numXss[x][y] = 1
    numYss = [[0]*(M-1) for _ in range(N)]
    for x, As in enumerate(Ass):
        for y in range(M-1):
            if As[y]&As[y+1]:
                numYss[x][y] = 1

    accAss = getAccAss(Ass)
    accNumXss = getAccAss(numXss)
    accNumYss = getAccAss(numYss)

    anss = []
    for _ in range(Q):
        x1, y1, x2, y2 = map(int, input().split())
        x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
        ans = getRangeSum2D(accAss, x1, x2, y1, y2)
        ans -= getRangeSum2D(accNumXss, x1, x2-1, y1, y2)
        ans -= getRangeSum2D(accNumYss, x1, x2, y1, y2-1)
        anss.append(ans)

    print('\n'.join(map(str, anss)))

solve()


### FIXED CODE ###

def solve():
    import sys
    input = sys.stdin.readline

    N, M, Q = map(int, input().split())
    Sss = [input().rstrip() for _ in range(N)]

    numVertexss = [[0]*(M+1)] + [[0] + list(map(int, Ss)) for Ss in Sss]
    numEdgeVss = [[0]*(M+1) for _ in range(N+1)]
    numEdgeHss = [[0]*(M+1) for _ in range(N+1)]
    for i in range(1, N):
        for j in range(1, M+1):
            if numVertexss[i][j] and numVertexss[i+1][j]:
                numEdgeVss[i][j] = 1
    for i in range(1, N+1):
        for j in range(1, M):
            if numVertexss[i][j] and numVertexss[i][j+1]:
                numEdgeHss[i][j] = 1

    def getAccAss(Ass):
        for x in range(1, N+1):
            for y in range(M+1):
                Ass[x][y] += Ass[x-1][y]
        for x in range(N+1):
            for y in range(1, M+1):
                Ass[x][y] += Ass[x][y-1]
    def getRangeSum2D(accAss, xFr, xTo, yFr, yTo):
        return accAss[xTo+1][yTo+1] - accAss[xTo+1][yFr] - accAss[xFr][yTo+1] + accAss[xFr][yFr]

    getAccAss(numVertexss)
    getAccAss(numEdgeVss)
    getAccAss(numEdgeHss)

    anss = []
    for _ in range(Q):
        x1, y1, x2, y2 = map(int, input().split())
        x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
        ans = getRangeSum2D(numVertexss, x1, x2, y1, y2)
        ans -= getRangeSum2D(numEdgeVss, x1, x2-1, y1, y2)
        ans -= getRangeSum2D(numEdgeHss, x1, x2, y1, y2-1)
        anss.append(ans)

    print('\n'.join(map(str, anss)))


solve()
n,p=map(int,input().split())
for i in range(int(p**(1/n)+1)):
  if p%i**n==0:exit(print(i))

### FIXED CODE ###

n,p=map(int,input().split())
for i in range(int(p**(1/n)+(p>n**2)),0,-1):
  if p%i**n==0:exit(print(i))
N = int(input() )
for i in range(N):
  C[i] = [map(int, input().split() ) ]
 
C.sort(key= lambda s:(s[1],s[0]) )
 
judge = "Yes"
time = 0
for i in range(N):
  time += C[i][0]
  if time > C[i][1]:
    judge = "No"
    break
print(judge)

### FIXED CODE ###

N = int(input() )
C = []
for i in range(N):
  A, B = map(int, input().split() )
  C.append([A, B])
C.sort(key=lambda s:s[1] )
 
judge = "Yes"
time = 0
for i in range(N):
  time += C[i][0]
  if time > C[i][1]:
    judge = "No"
    break
print(judge)
a,b=map(int,input().split())
if a+b=15:print("+")
elif a*b=15:print("*")
else:print("x")

### FIXED CODE ###

a,b=map(int,input().split())
if a+b==15:print("+")
elif a*b==15:print("*")
else:print("x")
s1 = input()
t1 = input()

s = list(s1)
t = list(t1)

flag = 0
for i in range(len(s)):
    for j in range(len(s)):
        if s[i] == s[j]:
            if t[i] == t[j]:
                a = 1
            else:
                print("No")
                flag = 1
                break
        if flag == 1:
            break

        if t[i] == t[j]:
            if s[i] == s[j]:
                a = 1
            else:
                print("No")
                flag = 1
                break
        if flag == 1:
            break
    if flag == 1:
        break
if flag == 0:
    print("Yes")


### FIXED CODE ###

d = input().split()

a = int(d[0])
b = int(d[1])
c = int(d[2])

e = 0

e = a*10+b+c

if e < b*10+a+c:
    e = b*10+a+c
    if e < c*10+a+b:
        e = c*10+a+b

if e < c*10+a+b:
    e= c*10+a+b
    if e < b*10+a+c:
        e = b*10+a+c

print(e)
N,Q = map(int,input().split())
path = [[] for i in range(N)]
ans = [0] * N
def dfs(v,p=-1):
    for to in path[v]:
        if to == p :
            continue
        ans[to] += ans[v]
        dfs(to,v)

for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a].append(b)
    path[b].append(a)
for i in range(Q):
    P,X = map(int,input().split())
    ans[P-1] += X
dfs(0)
print(*ans)

     

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7) 

N,Q = map(int,input().split())
path = [[] for i in range(N)]
ans = [0] * N
def dfs(v,p=-1):
    for to in path[v]:
        if to == p :
            continue
        ans[to] += ans[v]
        dfs(to,v)

for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a].append(b)
    path[b].append(a)
for i in range(Q):
    P,X = map(int,input().split())
    ans[P-1] += X
dfs(0)
print(*ans)
a,b = map(int, input().split())

m=a-2b



### FIXED CODE ###

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

m=a-2*b

if m>=0:
  print(m)
else:
  print(0)
s = input()
t = input()
for _ in range(len(s)):
    a = s[len(s)-1]
    b = [s[i] for i in range(len(s)-1)]
    bb = "".join(b)
    s = a+bb
    if s == t:
        print("Yes")
        exit()
print("No")

### FIXED CODE ###

data = sorted(list(map(int, input().split())))

print(data[2] - data[0])
A,B,K = map(int, input().split())
X = list(range(A,B+1))
ans = X[:K] + X[-K:]

for _ in set(ans):
  print(_)

### FIXED CODE ###

A,B,K = map(int, input().split())
X = range(A,B+1)

for _ in sorted(set(X[:K]) | set(X[-K:])):
  print(_)
isprime :: Int -> Bool
isprime 1 = False
isprime 2 = True
isprime n = not $ or (map ((0==).(mod n)) [2..ceil])
    where ceil = ceiling (sqrt (fromIntegral n))

getNLines :: Int -> IO [String]
getNLines n = do
    ans <- sequence $ take n (repeat getLine)
    return ans

main = do
    n <- getLine >>= return . read
    numbers <- getNLines n
    let integers = map read numbers
    print $ foldl (\acc x -> if isprime x then acc+1 else acc) 0 integers 




### FIXED CODE ###

#coding: UTF-8
def isPrime(n):
  if n == 1:
    return False
  import math
  m = math.floor(math.sqrt(n))
  for i in range(2,m+1):
    if n % i == 0:
      return False
  return True

n = int(input())
count = 0
for j in range(n):
  m = int(input())
  if isPrime(m):
    count += 1

print(count)
[a, b] = read().split().map(int)
print(a + b if b % a == 0 else b - a)


### FIXED CODE ###

[a, b] = map(int, input().split())
print(a + b if b % a == 0 else b - a)
import sys
S = input()
T = "AKIHABARA"
pos = 0
for x in S:
    if pos >= len(T):
        print("NO")
        sys.exit()
    if x == T[pos]:
        pos += 1
    elif T[pos] == 'A':
        pos += 1
        if x == T[pos]:
            pos += 1
        else:
            print("NO")
            sys.exit()
    else:
        print("NO")
        sys.exit()
print("YES")

### FIXED CODE ###

import sys
S = input()
T = "AKIHABARA"
posS = 0
posT = 0
while True:
    if posS == len(S):
        if posT >= len(T)-1:
            print("YES")
        else:
            print("NO")
        sys.exit()
    if posT >= len(T):
        print("NO")
        sys.exit()
    if S[posS] == T[posT]:
        posS += 1
        posT += 1
    elif T[posT] == 'A':
        posT += 1
    else:
        print("NO")
        sys.exit()
N, K, S = map(int,input().split())
L = [S]*K
for i in range(N-K):
  L.append(S+1)
  
print(' '.join(map(int, L)))

### FIXED CODE ###

N, K, S = map(int,input().split())
L = [S]*K
for i in range(N-K):
  if S < 10**9:
  	L.append(S+1)
  else:
    L.append(1)
  
print(' '.join(map(str, L)))
s = input().split()
n = int(s)
sum = 0
for i range(1,n+1):
  print(n)
  if ((i mod 3 )!=0 ) and ((i mod 5 )!=0 ) :
    sum += i
print(sum)


### FIXED CODE ###

s = input().split()
n = int(s[0])
sum = 0
for i in range(1,n+1):
  #print(n)
  if ((i % 3 )!=0 ) and ((i % 5 )!=0 ) :
    sum += i
print(sum)
N, M = map(int, input().split())
 
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

if N < 2:
  a = cmb(M,2)
elif M < 2:
  a = cmb(N,2)
elif N > 1 and M > 1:
  a = cmb(N,2) + cmb(M,2)
else:
  a = 0

print(int(a))


### FIXED CODE ###

N, M = map(int, input().split())
 
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

if N < 2 and M < 2:
  a = 0
elif N < 2:
  a = cmb(M,2)
elif M < 2:
  a = cmb(N,2)
elif N > 1 and M > 1:
  a = cmb(N,2) + cmb(M,2)

print(int(a))
a=list(map(int, input().split()))
if a[0]+a[1]>=a[2]＊2:
    if a[3]>=a[4]:
        print (a[2]＊a[4]＊2+a[0]＊(a[3]-a[4]))
    else:
        print (a[2]＊a[3]＊2+a[1]＊(a[4]-a[3]))
else:
    print (a[0]＊a[3]+a[1]＊a[4])


### FIXED CODE ###

a, b, c, x, y = map(int, input().split())
res = 0
if a+b > c*2:
    mi = min(x, y)
    res += c*2 * mi
    x -= mi
    y -= mi
res += x * min(a, c*2)
res += y * min(b, c*2)
print(res)
import numpy as np
import math

n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

if k == 0:
    print(0)
    quit()

logk = math.ceil(math.log2(k))
half = n / 2

base = np.array([2**i for i in range(logk)])

a = np.array(a)

ones = a[:,None] & base > 0
# zeros = ones != True

no = np.sum(ones, axis=0)
# nz = np.sum(zeros, axis=0)

# print(no)
# print(nz)

v = no < half
vi = np.sum(v * base)

index = 0
while vi > k:
    flip = not (index & base)
    tmp = v.copy()
    tmp &= flip
    index += 1
    vi = np.sum(tmp * base)

# print(vi)

print(np.sum(a ^ vi))


### FIXED CODE ###

import numpy as np
import math

_, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

logk = 50
half = len(a) / 2

base = np.array([2**i for i in range(logk + 1)])

a = np.array(a)

ones = a[:,None] & base > 0
zeros = (ones != True)

# print(base[:5])
# print(ones)
# print(zeros)

no = np.sum(ones, axis=0)
nz = np.sum(zeros, axis=0)

ov = no * base
zv = nz * base

# print(no)
# print(nz)

inc = ov < zv

inceq = ov == zv
# vi = np.sum(v * base)


# def largest(fx, kk, i):
#     if i == len(base):
#         return fx

#     kone = kk + base[i]
#     if kone > k:
#         return fx

#     kzero = kk
#     fzero = fx + ov[i]
#     fone = fx + zv[i]
#     return max(largest(fzero, kzero, i + 1), largest(fone, kone, i + 1))

# print(largest(0, 0, 0))

kk = [0]
fx = [0]
for i, b in reversed(list(enumerate(base))):
    for j in range(len(fx)):
        added = kk[j] + b
        if (inc[i] or inceq[i]) and added <= k:
            if inceq[i]:
                fx.append(fx[j] + ov[i])
                kk.append(kk[j])
            fx[j] += zv[i]
            kk[j] += b

        else:
            fx[j] += ov[i]

print(max(fx))
import math

N = int(input())
x = int(input())
T = int(input())

print(str(T * math.ceil(N / x)))

### FIXED CODE ###

import math

N, x, T = map(int, input().split())

print(math.ceil(N / x) * T)
def main():
    input()
    H=map(int,input().split())
    A=map(int,input().split())
    n=10*5+1

    def update_max(k,x):
        k += num_max-1
        seg_max[k] = x
        while k:
            k = (k-1)//2
            seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    def query_max(p,q):
        if q<=p:
            return ide_ele_max
        p += num_max-1
        q += num_max-2
        res=ide_ele_max
        while q-p>1:
            if p&1 == 0:
                res = max(res,seg_max[p])
            if q&1 == 1:
                res = max(res,seg_max[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = max(res,seg_max[p])
        else:
            res = max(max(res,seg_max[p]),seg_max[q])
        return res
    ide_ele_max = 0
    num_max =2**(n-1).bit_length()
    seg_max=[ide_ele_max]*2*num_max

    for h,a in zip(H,A):
        update_max(h,query_max(0,h)+a)
    
    print(query_max(0,n))
main()

### FIXED CODE ###

def main():
    input()
    H=map(int,input().split())
    A=map(int,input().split())
    n=2*10**5+1

    def update_max(k,x):
        k += num_max-1
        seg_max[k] = x
        while k:
            k = (k-1)//2
            seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    def query_max(p,q):
        if q<=p:
            return ide_ele_max
        p += num_max-1
        q += num_max-2
        res=ide_ele_max
        while q-p>1:
            if p&1 == 0:
                res = max(res,seg_max[p])
            if q&1 == 1:
                res = max(res,seg_max[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = max(res,seg_max[p])
        else:
            res = max(max(res,seg_max[p]),seg_max[q])
        return res
    ide_ele_max = 0
    num_max =2**(n-1).bit_length()
    seg_max=[ide_ele_max]*2*num_max

    for h,a in zip(H,A):
        update_max(h,query_max(0,h)+a)
    
    print(query_max(0,n))
main()
from math import log10
N = int(input())
ans = []
for i in range(1,int(log10(N))+1):
    ans.append((sum(map(int,list(str((int(N/(10**i))*(10**i)-1)))))))
print(max(ans))

### FIXED CODE ###

N = list(map(int,str(input())))
N_ = N[1:]
ans = N[0]+(9*len(N_))
if all([N_[i] == 9 for i in range(len(N_))]):
    print(ans)
else:
    print(ans-1)
import math
def combi(n,r):
  ans = math.factorial(N) // (math.factorial(n-r) * math.factorial(r))
  return ans

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

ans = 0
ans += combi(M,2)
ans += combi(N,2)
print(ans)


### FIXED CODE ###

import math
def combi(n,r):
  ans = math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
  return ans

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

ans = 0
if N > 1:
  ans += combi(N,2)
if M > 1:
  ans += combi(M,2)
print(ans)
n=int(input())
a,b,c=[map(list,map(int,input().split())) for _ in range(3)] 
x=0
for i,_ in enumerate(a):
  if(i==len(a)-1):
    break
  elif(a[i]+1==a[i+1]):
    x+=c[a[i]-1]
print(sum(b)+x)

### FIXED CODE ###

n=int(input())
a,b,c=[list(map(int,input().split())) for _ in range(3)] 
x=0
for i,_ in enumerate(a):
  if(i==len(a)-1):
    break
  elif(a[i]+1==a[i+1]):
    x+=c[a[i]-1]
print(sum(b)+x)
A, B, C = input().split()
# l = A[-1] 
# v = B[0]
# n = B[-1]
# s = C[0]
# if l == v and v == n and n == s:
if (A[-1]) == (B[0]) and (B[-1]) == (C[0])
    print("Yes")
else:
    print("No")

### FIXED CODE ###

A, B, C = input().split()
if (A[-1]) == (B[0]) and (B[-1]) == (C[0]):
    print("YES")
else:
    print("NO")
k,x = map(int,input().split())

lis = [x]

for i in range(1,k):
    lis.append(x-1)
    lis.append(x+1)
new_list = sorted(lis)

print(" ".join(new_list))

### FIXED CODE ###

k,x = map(int,input().split())

lis = []
for i in range(x-k+1, x+k):
    lis.append(i)

print(" ".join(map(str,lis)))
import sys
input = sys.stdin.readline
n, k = [ int(v) for v in input().split() ]
card_parent = [ i for i in range(n) ]
card_set = [ set([i]) for i in range(n) ]
card_list = [ tuple( int(v)-1 for v in input().split() ) for i in range(k) ]

def parent(x):
    if card_parent[x] == x:
        return x
    else:
        return parent(card_parent[x])


for i in card_list:
    p, q = i[0], i[1]
    card_parent[p] = parent(p)
    card_parent[q] = parent(q)
    if card_parent[p] != card_parent[q]:
        if p < q:
            card_parent[card_parent[q]] = card_parent[p]
        else:
            card_parent[card_parent[p]] = card_parent[q]




card_parent = [ parent(i) for i in range(n) ]

print(len(set(card_parent)))

### FIXED CODE ###


import sys
input = sys.stdin.readline
n, k = [ int(v) for v in input().split() ]
card_parent = [ i for i in range(n) ]
card_set = [ set([i]) for i in range(n) ]
card_list = [ tuple( int(v)-1 for v in input().split() ) for i in range(k) ]

def parent(x,a):
    if card_parent[x] == x:
        return x, a
    else:
        return parent(card_parent[x],a+1)


for i in card_list:
    p, q = i[0], i[1]
    card_parent[p], rank_p = parent(p,0)
    card_parent[q], rank_q = parent(q,0)
    if card_parent[p] != card_parent[q]:
        if rank_p > rank_q:
            card_parent[card_parent[q]] = card_parent[p]
        else:
            card_parent[card_parent[p]] = card_parent[q]




card_parent = [ parent(i,0)[0] for i in range(n) ]

print(len(set(card_parent)))
N = int(input())
H = list(map(int, input().split()))
max = 0

for i in range(N):
  cnt = 0
  if i != N-1:
    now = i
    while H[now] <= H[now+1]:
      now += 1
      cnt += 1
      if now < 0:
        break
    if max < cnt:
      max = cnt
  cnt = 0
  if i != 0:
    now = i
    while H[now] <= H[now-1]:
      now -= 1
      cnt += 1
      if now > N-1:
        break
    if max < cnt:
      max = cnt
print(max)


### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
H.reverse()
max = 0
cnt = 0
 
for i in range(N-1):
  if H[i] <= H[i+1]:
    cnt += 1
  else:
    cnt = 0
  if cnt > max:
    max = cnt
if cnt > max:
  max = cnt
print(max)
x, y = map(int, input().split())

#print(a ,type(a))
if x<10:
    print(y+(100*(10-x)))
else:
    print(y)


### FIXED CODE ###

x, y = map(int, input().split())

#print(a ,type(a))
if x<10:
    print(y+(100*(10-x)))
else:
    print(y)
a = int(input())

b = []

for i in range(a):
    b.append(input().split())

res = 0

for i in b:
    if (i[1] == 'BTC'):
        res += i[0]*380000
    else:
        res += i[0]

print(res) 

### FIXED CODE ###

a = str(input())

a = a[:4] + a[5:7] + a[8:]

a = int(a)

if (a > 20190430):
    print('TBD')
else:
    print('Heisei')
A,B=map(int,input().split())
if A==B:
    print("Draw")
elif (A>B or A:
    print("Alice")
else:
    print("Bob")

### FIXED CODE ###

As=list(map(int,input().split()))

for A in range(2):
    if As[A]==1:
        As[A]+=13
        
if As[0]==As[1]:
    print("Draw")
elif As[0]>As[1]:
    print("Alice")
else:
    print("Bob")
N = int(input())
L = tuple(map(int, input().split()))
res = 0
def dfs(A):
    global res, L
    ans = [i for i, v in enumerate(A) if v == 1]
    if len(A) > N:
        return 
    elif len(ans) == 3:
        a, b, c = L[ans[0]], L[ans[1]], L[ans[2]]
        if a < (b + c) and b < (c + a) and c < (a + b):
            res += 1
        return
    else:
        for v in range(2):
            A.append(v)
            dfs(A)
            A.pop()
dfs([])
print(res)

### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
ans = 0
L.sort()
for a_i in range(N-2):
    for b_j in range(a_i+1, N-1):
        c_idx = bisect.bisect_left(L, L[a_i]+L[b_j])
        if c_idx > b_j:
            ans += c_idx - b_j - 1
print(ans)
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
edge = [[] for i in range(n)]
alledge = []
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    alledge.append([a-1,b-1])
if n==2:
    print(0)
    exit()


def f(x,y,c):
    c += 1
    for e in edge[x]:
        if e != y:
            if c > d and e >= 0 and e<= n-1:
                used[e] = 1
            if len(edge[e])>=2:
                f(e,x,c)


if k % 2 == 0:
    d = k//2
    res = []
    for i in range(n):
        used = [0]*n
        f(i,-1,0)
        res.append(sum(used))
    print(min(res))
else:
    d = (k-1)//2
    res = []
    for e1 in alledge:
        used = [0]*n
        f(e1[0],e1[1],0)
        f(e1[1],e1[0],0)
        res.append(sum(used))
    print(min(res))


### FIXED CODE ###

import sys
#input = sys.stdin.readline
n,k = map(int,input().split())
edge = [[] for i in range(n)]
alledge = []
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    alledge.append((a-1,b-1))

def f(x,y,c):
    global tmp
    c += 1
    for e in edge[x]:
        if e == y:
            continue
        if c > d:
            tmp +=1
        f(e,x,c)

sys.setrecursionlimit(4100000)

if k % 2 == 0:
    d = k//2
    ass = 2001
    for i in range(n):
        tmp = 0
        f(i,-1,0)
        ass = min(ass,tmp)
    print(ass)
else:
    d = (k-1)//2
    ass = 2001
    for e1 in alledge:
        tmp = 0
        f(e1[0],e1[1],0)
        f(e1[1],e1[0],0)
        ass = min(ass,tmp)
    print(ass)
# -*- coding: utf-8 -*-
# 入力
N = str(input())
#X, Y = map(str, input().split())

if N[0] == N[1] and N[1] == N[2] :
  print ("Yes")1234
elif N[1] == N[2] and N[2] == N[3]:
  print ("Yes")
else :
  print ("No")


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 入力
N = str(input())
#X, Y = map(str, input().split())

if N[0] == N[1] and N[1] == N[2] :
  print ("Yes")
elif N[1] == N[2] and N[2] == N[3]:
  print ("Yes")
else :
  print ("No")
S = int(input() S >= 10000)
s = int(input())
a = int(h = (S / 3600), m = ((S % 3600) / 60), for s in range(0, 60):)
print('a')

### FIXED CODE ###

S = int(input())

s = S % 60
m = S // 60 % 60
h = S // 60 // 60

print("{0}:{1}:{2}".format(h,m,s))
n,x = map(int,input().split())
x_list = list(map(int,input().split()))
import math
import functools
x_list.append(x)
x_list = sorted(x_list)
a = []
for i in range(n):
    b = x_list[i+1]-x_list[i]
    a.append(b)
gcd = functools.reduce(math.gcd,a)
print(gcd)

### FIXED CODE ###

n,x = map(int,input().split())
x_list = list(map(int,input().split()))
x_list.append(x)
x_list = sorted(x_list)
a = []
for i in range(n):
    b = x_list[i+1]-x_list[i]
    a.append(b)
import math
from functools import reduce
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
ans = reduce(gcd, a)
print(int(ans))
# import sys
# input = sys.stdin.readline

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

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

graph = [[float('inf') for _ in range(n)] for _ in range(n)]


for a, b, c in abc:
    graph[a-1][b-1] = c 
    graph[b-1][a-1] = c
for i in range(n):
    graph[i][i] = 0

# print(graph)

def warshall_floyd(graph):
    d = graph.copy()
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

graph = warshall_floyd(graph)

for i in range(n):
    for j in range(n):
        if 0 < graph[i][j] <= l:
            graph[i][j] = 1
        if graph[i][j] > l:
            graph[i][j] = float('inf')

graph = warshall_floyd(graph)

for s, t in st:
    print(graph[s-1][t-1]-1 if graph[s-1][t-1] != float('inf') else -1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
n, m, l = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]
q = int(input())
 
st = [list(map(int, input().split())) for _ in range(q)]
 
graph = [[float('inf') for _ in range(n)] for _ in range(n)]
 
 
for a, b, c in abc:
    graph[a-1][b-1] = c 
    graph[b-1][a-1] = c
for i in range(n):
    graph[i][i] = 0
 
# print(graph)
 
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d
 
graph = warshall_floyd(graph)
 
for i in range(n):
    for j in range(n):
        if 0 < graph[i][j] <= l:
            graph[i][j] = 1
        if graph[i][j] > l:
            graph[i][j] = float('inf')
 
graph = warshall_floyd(graph)
 
for s, t in st:
    print(graph[s-1][t-1]-1 if graph[s-1][t-1] != float('inf') else -1)