Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)
        NP[a][b] = 0
        NP[b][a] = 0
        ZO[a][b] = L - c
        ZO[b][a] = L - c

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)

up = [False] + [True for _ in range(N)]
while up.count(True) > 0:
    for i in range(1,N+1):
        if up[i] == False : continue
        up[i] = False
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for d,c in zip(rd[j], rc[j]):
                if d == i: continue
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up[i] = True

for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq


def wf(d,n):
    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

def main():
    INF = 10**18
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,L = LI()
    road = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        if c <= L:
            road[a-1][b-1] = c
            road[b-1][a-1] = c

    road = wf(road,N)


    gas = [[INF] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if road[i][j] <= L:
                gas[i][j] = 1

    gas = wf(gas,N)

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        if gas[s-1][t-1] == INF:
            print(-1)
        else:
            print(gas[s-1][t-1]-1)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, Q = map(int,input().split())
S = str(input())
for i in range(Q):
    l, r = map(int,input().split())
    S_tmp = S[l-1:r]
    print(S_tmp.count("AC"))


### FIXED CODE ###

N, Q = map(int,input().split())
S = str(input())
count = 0
li = [0]
for i in range(N-1):
    if S[i:i+2] == "AC":
        count += 1
    li.append(count)
for i in range(Q):
    l,r = map(int,input().split())
    print(li[r-1]-li[l-1])
### BUGGY CODE ###

N=int(input())
dp=[-1]*(N+1)
dp[0]=0
que=[0]
while len(que)!=0:
    v=que[0]
    que=que[1:]
    pow6=1
    while v+pow6<=N:
        if dp[v+pow6]==-1:
            dp[v+pow6]=dp[v]+1
            que.append(v+pow6)
        pow6*=6
    pow9=1
    while v+pow9<=N:
        if dp[v+pow9]==-1:
            dp[v+pow9]=dp[v]+1
            que.append(v+pow9)
        pow9*=9
print(dp[N])

### FIXED CODE ###

N=int(input())
dp=[N]*(N+1)
dp[0]=0
for i in range(1,N+1):
    dp[i]=min(dp[i],dp[i-1]+1)
    pow6 = 1
    while i>=pow6:
        dp[i]=min(dp[i],dp[i-pow6]+1)
        pow6*=6
    pow9 = 1
    while i>=pow9:
        dp[i]=min(dp[i],dp[i-pow9]+1)
        pow9*=9
print(dp[N])
### BUGGY CODE ###

from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

from collections import deque

def main():
    v, e = map(int, readline().split())
    g = [[float('inf')] * v for _ in range(v)]
    for _ in range(e):
        s, t, d = map(int, readline().split())
        g[s][t] = d
    min_cost = float('inf')

    que = deque([(0, 0, set(range(1, v)))])
    while que:
        cost, last, vs = que.pop()
        if min_cost <= cost:continue
        if vs:que.extend((cost + g[last][v], v, vs - {v}) for v in vs)
        elif min_cost > cost + g[last][0]:min_cost = cost + g[last][0]

    print(-1 if isinf(min_cost) else min_cost)

main()

### FIXED CODE ###

# http://www.geocities.jp/m_hiroi/light/pyalgo65.html

def memoize(f):
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memoize
def tsp(p, v):
    if (1 << point_size) - 1 == v:
        return distance_table[p][0]
    else:
        return min(distance_table[p][x] + tsp(x, v | (1 << x)) for x in range(point_size) if not (v & (1 << x)))

from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

point_size, e = map(int, readline().split())
distance_table = [[float('inf')] * point_size for _ in range(point_size)]
for _ in range(e):
    s, t, d = map(int, readline().split())
    distance_table[s][t] = d
ans = tsp(0,1)
print(-1 if isinf(ans) else ans)
### BUGGY CODE ###

N = int(input())
A = [None] * N
for i in range(N):
    A[i] = int(input())

for i in range(N):
    a = A[i]
    A[i] = 0
    ans = max(A)
    print(ans)
    A[i] = a

### FIXED CODE ###

N = int(input())
A = [None] * N
for i in range(N):
    A[i] = int(input())

l = sorted(A)
b = l[-1]
c = l[-2]

for i in range(N):
    if A[i] == b:
        print(c)
    else:
        print(b)
### BUGGY CODE ###

n = int(input())
s = input()

ans = 0
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                if j - i != k - j:
                    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

ans = s.count("R")*s.count("G")*s.count("B")
for i in range(n):
    for j in range(i+1,n):
        k = 2*j-i
        if k < n and s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

n,m=list(map(int, input().split()))
a=list(map(int,input().split()))
for _ in range(m):
  a[a.index(max(a))] = max(a) // 2
print(sum(a))

### FIXED CODE ###

n,m=list(map(int, input().split()))
a=list(map(int, input().split()))
a.sort(reverse=True)
while m>0:
  a[0] //= 2
  m = m - 1
  for i in range(n-1):
    if a[0] < a[i+1] and m > 0:
      a[i+1] //= 2
      m = m - 1
    else:
      a.sort(reverse=True)
      break
print(sum(a))
### BUGGY CODE ###

from sys import stdin
N, M = map(int, input().split())
seki = set(list(range(1,N+1)))
for i in range(M):
    l, r = map(int, stdin.readline().rstrip().split())
    seki &= set(list(range(l, r+1)))

print(len(seki))

### FIXED CODE ###

# 解説を見ての解答
from sys import stdin

n, m = map(int, stdin.readline().rstrip().split())
lr = [list(map(int, stdin.readline().rstrip().split())) for i in range(m)]

l, r = lr[0][0], lr[0][1]
for i in range(m):
    l = max(l, lr[i][0])
    r = min(r, lr[i][1])

print(max(0,r-l+1))
### BUGGY CODE ###

from collections import Counter

N = int(input())
S = input()

left, right = S[:N], S[N:][::-1]
a, b = Counter(), Counter()

for i in range(2 ** N):
    t = "".join(left[j] if (i >> j) & 1 else "" for j in range(N))
    u = "".join(right[j] if (i >> j) & 1 else "" for j in range(N))
    v = "".join("" if (i >> j) & 1 else left[j] for j in range(N))
    w = "".join("" if (i >> j) & 1 else right[j] for j in range(N))
    a[t, v] += 1
    b[u, w] += 1

print((sum(a[t] * b[t] for t in a.keys())))

### FIXED CODE ###

from collections import Counter

N = int(input())
S = input()

left, right = S[:N], S[N:][::-1]
a, b = Counter(), Counter()

for i in range(2 ** N):
    t = "".join(left[j] if (i >> j) & 1 else "" for j in range(N))
    u = "".join(right[j] if (i >> j) & 1 else "" for j in range(N))
    v = "".join("" if (i >> j) & 1 else left[j] for j in range(N))
    w = "".join("" if (i >> j) & 1 else right[j] for j in range(N))
    a[t, v] += 1
    b[u, w] += 1

print((sum(a[t] * b[t] for t in a.keys())))
### BUGGY CODE ###

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

medium = 1
for k in range(K):
    medium = medium*A[k]

for i in range(K,N):
    medium2 = medium/A[i-K]*A[i]
    if(medium < medium2):
        print("Yes")
    else:
        print("No") 
    medium = medium2

### FIXED CODE ###

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

for i in range(K,N):
    if(A[i-K] < A[i]):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
n=n//2+1
ans="YES"
for i in range(n):
  num=a[i]
  if a.count(num)!=1:
    ans="NO"
    break
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans="YES"
for i in range(n-1):
  if a[i]==a[i+1]:
    ans="NO"
    break
print(ans)
### BUGGY CODE ###

s = str(input())
q = int(input())

for i in range(q):
    x = input().split()
    if x[0] == '1':
        s = s[::-1]
    elif x[1] == '1':
        s = x[2] + s
    else:
        s = s + x[2]
print(s)

### FIXED CODE ###

s = str(input())
q = int(input())

x = []
pre = ''
post = ''
isone = False
for i in range(q):
    x = input().split()
    if x[0] == '1':
        if isone:
            isone = False
        else:
            isone = True
    elif x[1] == '1':
        if isone:
            post += x[2]
        else:
            pre += x[2]
    else:
        if isone:
            pre +=x [2]
        else:
            post += x[2]
    if i == q - 1:
        if isone:
            s = post[::-1] + s[::-1] + pre
        else:
            s = pre[::-1] + s + post
print(s)
### BUGGY CODE ###

import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a_origin = sorted(inpl())
ans = 0
count = collections.defaultdict(int)
a = []
for i in range(n):
    count[a_origin[i]] += 1
    if count[a_origin[i]] < 3:
        a.append(a_origin[i])
n = len(a)


class Cell:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None


prev = Cell(a[0])
now = prev
for i in range(1, n):
    new = Cell(a[i])
    prev.next = new
    new.prev = prev
    prev = prev.next
while now:
    if not now.next:
        ans += 1
        break
    target = now.next
    while target:
        if target.value == now.value:
            ans -= 1
        if target.value % now.value == 0:
            if target.next:
                target.next.prev = target.prev
                target.prev.next = target.next
            else:
                target.prev.next = None
        target = target.next
    ans += 1
    now = now.next
print(ans)


### FIXED CODE ###

import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a = sorted(inpl())
cnt = collections.Counter(a)
ans = 0
dp = [0] * (10**6 + 1)
for i in a:
    if dp[i] == 0:
        for j in range(1, 10**7):
            if i * j > 10**6:
                break
            dp[i * j] = 1
        if cnt[i] == 1:
            ans += 1
print(ans)
### BUGGY CODE ###

def main():
    N , K = map(int, input().split())

    A_list = [A for A in input().split()]
    A_list = list(map(int, A_list))

    import itertools
    p = itertools.permutations(A_list, K)
    ans = 100000000000
    for val in p :
        ans_new = sum(val)
        if ans_new < ans :
            ans = ans_new
        #print(val)

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N , K = map(int, input().split())

    A_list = [A for A in input().split()]
    A_list = list(map(int, A_list))

    A_list.sort()
    #print(A_list)
    ans = 0
    for i in range(0,K) :
        ans = ans + A_list[i]

    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

a, b, m = map(int, input().split())
a1 = list(map(int, input().split()))
b1 = list(map(int, input().split()))

disc = [list(map(int, input().split())) for i in range(m)]

ans = []
from collections import deque
ans = deque(ans)

ans1 = [x+y for x in a1 for y in b1]

for i in range(m):
    ans.append( a1[disc[i][0]-1] + b1[disc[i][1]-1] - disc[i][2] )

ans = list(ans)
ans = ans + ans1
print(min(ans))




### FIXED CODE ###

a, b, m = map(int, input().split())
a1 = list(map(int, input().split()))
b1 = list(map(int, input().split()))

disc = [list(map(int, input().split())) for i in range(m)]
import numpy as np


from collections import deque
ans = []

ans = deque(ans)

for i in range(m):
    ans.append( a1[disc[i][0]-1] + b1[disc[i][1]-1] - disc[i][2] )

ans = list(ans)

print(min( min(ans), min(a1)+min(b1) ))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
f = [0] * N
for i in range(1, N+1):
  count = 0
  for x in range(1, i):
    for y in range(x, i):
      z = i-x-y
      if z < y:
        break
      n = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if n > N:
        continue
      if x == y and x == z:
        f[n-1] += 1
      elif x == y or y == z:
        f[n-1] += 3
      elif x != y and x != z and y != z:
        f[n-1] += 6
for i in f:
  print(i)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math

N = int(input())
f = [0] * N
for i in range(1, N+1):
  count = 0
  for x in range(1, i):
    if x**2 > N:
      break
    for y in range(x, i):
      if y**2 > N:
        break
      z = i-x-y
      if z < y:
        break
      n = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if z > math.sqrt(n + 1):
        break
      if n <= N:
        if x == y and x == z:
          f[n-1] += 1
        elif x == y or y == z:
          f[n-1] += 3
        elif x != y and x != z and y != z:
          f[n-1] += 6
for i in f:
  print(i)
### BUGGY CODE ###

from collections import deque

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]
C = [c for b, c in BC for _ in range(b)]
A.sort()
C.sort(reverse=True)
d = deque([])
# d.extend(C[max(len(C)-N, 0):])
d.extend(C[:N])
# 
# print(A)
# print(d)

i = 0
while d:
    q = d.popleft()
    if q > A[i]:
        A[i] = q
        i += 1
    else:
        break

print(sum(A))


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]
BC = sorted(BC, key=lambda x: x[1])
A.sort()
i = 0
for b, c in BC[::-1]:
    for _ in range(b):
        if i == N:
            break
        if c > A[i]:
            A[i] = c
            i += 1
        else:
            break

print(sum(A))
### BUGGY CODE ###

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

for ki in range(k):
  if a >= 1:
    a -= 1
  elif b >= 1:
    b -= 1

print(a,b)

### FIXED CODE ###

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

if k < a:
  a = a-k

else:
  k = k-a
  a = 0
  if k < b:
    b = b-k
  else:
    b = 0
  
print(a,b)
### BUGGY CODE ###

number,money=input().rstrip().split()
number=int(number)
money=int(money)
bill=[0,0,0]

for i in range(number+1):
    bill=[0,0,0]
    mass=money-10000*i
    bill[0]=i
    if mass==0 and sum(bill)==number:
        break
    elif mass<0:
        break
    else:
        for j in range(number+1):
            if j!=0:
                mass=mass-5000
            bill[1]=j
            if mass==0 and sum(bill)==number:
                break
            elif mass<0:
                break
            else:
                k=int(mass/1000)
                bill[2]=k
                if sum(bill)==number:
                    mass=0
                    break
    if sum(bill)==number:
        break
                
if mass==0:
    print(str(bill[0])+' '+str(bill[1])+' '+str(bill[2]))
else:
    print(str(-1)+' '+str(-1)+' '+str(-1))


### FIXED CODE ###

number,money=input().rstrip().split()
number=int(number)
money=int(money)
bill=[0,0,0]

for i in range(number+1):
    bill=[0,0,0]
    mass=money-10000*i
    bill[0]=i
    if mass==0 and sum(bill)==number:
        break
    elif mass<0:
        break
    else:
        for j in range(number+1-i):
            if j!=0:
                mass=mass-5000
            bill[1]=j
            if mass==0 and sum(bill)==number:
                break
            elif mass<0:
                break
            else:
                k=int(mass/1000)
                bill[2]=k
                if sum(bill)==number:
                    break
    if sum(bill)==number:
        mass=0
        break
                
if mass==0:
    print(str(bill[0])+' '+str(bill[1])+' '+str(bill[2]))
else:
    print(str(-1)+' '+str(-1)+' '+str(-1))
### BUGGY CODE ###

rflag = 0
s = input()
q = int(input())

for i in range(q):
    x = input().split()
    
    if (x[0] == '1'):
        s = s[::-1]
    else:
        s = '%s%s'%(x[2],s) if (x[1] == '1') else '%s%s'%(s,x[2])
        '''
        if(x[1] == '1'):
            s = x[2] + s
        else:
            s += x[2]
        '''
print(s)


### FIXED CODE ###

from collections import deque

revFlag = False

s = deque(input())
q = int(input())

for i in range(q):
    a,b,c, *_ = input().split() + [None, None]
    
    if(a == '1'):
        revFlag = not revFlag
        
    else:
        b = int(b)
        if(revFlag):
            b = (int(b)%2)+1
        
        if(b == 1):
            s.appendleft(c)
        else:
            s.append(c)
            
    #print(_,*s, sep="")

if(revFlag):
    s.reverse()
    
print(*s, sep='')
### BUGGY CODE ###

q=int(input())
lr=[list(map(int,(str(_)+' '+input()).split())) for _ in range(q)]
#nの素数判定
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
lr.sort(key=lambda x:x[1])
ans=[]
l_=lr[0][1]
r_=lr[0][2]
a=[]
for i in range(l_,r_+1):
  if is_prime(i) and is_prime((i+1)//2):
    a.append(i)
ans.append([lr[0][0],a])
for i in range(1,q):
  r_=lr[i][2]
  a=[ai for ai in a if ai<l_]
  l_=lr[i][1] if len(a)==0 else a[-1]
  for j in range(l_,r_+1):
    if is_prime(j) and is_prime((j+1)//2):
      a.append(j)
  ans.append([lr[i][0],a])
ans.sort(key=lambda x:x[0])
for i in range(q):
  print(len(ans[i][1]))


### FIXED CODE ###

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
a=[]
for i in range(3,10**5):
  if is_prime(i) and is_prime((i+1)//2):
    a.append(i)
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
for lri in lr:
  print(len([ai for ai in a if ai>=lri[0] and ai<=lri[1]]))
### BUGGY CODE ###

from collections import deque
from heapq import heapify,heappop,heappush
n = int(input())
data = [[] for _ in range(n)]
color = [[-1]*n for _ in range(n)]
sides = []
for _ in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    data[a].append(b)
    data[b].append(a)
    sides.append((a,b))
kinds = -1
m = -1
for i in range(n):
    if kinds < len(data[i]):
        kinds = len(data[i])
        m = i
unused = [[i for i in range(1,kinds+1)] for _ in range(n)]
against = [[] for _ in range(n)]
for i in range(n):
    heapify(unused[i])
    heapify(against[i])
print(kinds)
q = deque([m])
visited = [0]*n
while q:
    p = q.popleft()
    visited[p] = 1
    for i in data[p]:
        if visited[i]:
            continue
        while against[p] and (unused[p][0] == against[p][0]):
            heappop(against[p])
            heappop(unused[p])
        color[p][i] = unused[p][0]
        color[i][p] = unused[p][0]
        q.append(i)
        heappush(against[i],heappop(unused[p]))
for i,j in sides:
    print(color[i][j])

### FIXED CODE ###

from collections import deque,defaultdict
n = int(input())
data = [[] for _ in range(n)]
sides = []
for _ in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    data[a].append(b)
    data[b].append(a)
    sides.append((a,b))
I = defaultdict(lambda:0)
cs = [0]*n
used = [0]*n
q = deque([0])
used[0]=1
k = 0
while q:
    u = q.popleft()
    if k < len(data[u]):
        k = len(data[u])
    cur = 1
    for v in data[u]:
        if used[v]:continue
        if cur==cs[u]:cur+=1
        cs[v] = cur
        I[(u,v)] = cur
        I[(v,u)] = cur
        cur += 1
        used[v] = 1
        q.append(v)
print(k)
for i,j in sides:
    print(I[(i,j)])
### BUGGY CODE ###

from scipy.sparse.csgraph import floyd_warshall
    
def solve(s,t,edge):
    edge = floyd_warshall(edge)

    for i in range(n):
        for j in range(n):
            if edge[i][j]<=l:
                edge[i][j] = 1
            else:
                edge[i][j] = 0

    edge = floyd_warshall(edge)

    if edge[s-1][t-1] == float("inf"):
        return -1
    else:
        return int(edge[s-1][t-1] - 1)
      
n,m,l = map(int,input().split())
edge = [[0]*n for _ in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    edge[a-1][b-1] = c
    edge[b-1][a-1] = c
    
q = int(input())
for i in range(q):
  s,t = map(int,input().split())
  print(solve(s,t,edge))

### FIXED CODE ###

import sys
input = sys.stdin.readline
from scipy.sparse.csgraph import floyd_warshall
      
n,m,l = map(int,input().split())
edge = [[0]*n for _ in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    edge[a-1][b-1] = c
    edge[b-1][a-1] = c

edge = floyd_warshall(edge)
    
for i in range(n):
    for j in range(n):
        if edge[i][j]<=l:
            edge[i][j] = 1
        else:
            edge[i][j] = 0
                
edge = floyd_warshall(edge)

q = int(input())
for i in range(q):
    s,t = map(int,input().split())
    if edge[s-1][t-1] == float("inf"):
        print(-1)
    else:
        print(int(edge[s-1][t-1] - 1))
### BUGGY CODE ###

N = int(input())
b = [int(x) for x in input().split()]

def solve(b):
    if len(b) == 0:
        return []
    for i in range(len(b)):
        if b[i] == i+1:
            a = solve(b[:i] + b[i+1:])
            if a != None:
                return [i+1] + a
    return None

a = solve(b)
if a == None:
    print(-1)
else:
    a.reverse()
    print('\n'.join(map(str, a)))


### FIXED CODE ###

N = int(input())
b = [int(x) for x in input().split()]

def solve(b):
    if len(b) == 0:
        return []
    if any(i+1 < b[i] for i in range(len(b))):
        return None
    erasable = [i+1 for i in range(len(b)) if i+1 == b[i]]
    if len(erasable) == 0:
        return None
    i = erasable[-1]  # 一番右から消す
    a = solve(b[:i-1] + b[i:])
    if a != None:
        return [i] + a
    return None

a = solve(b)
if a == None:
    print(-1)
else:
    a.reverse()
    print('\n'.join(map(str, a)))
### BUGGY CODE ###

n=int(input())
arr=input()
prod=1
l=list(map(int,arr.split(' ')))
for x in l:
    prod*=x
    
if(prod>1000000000000000000):
    print(-1)
else:
    print(prod)




### FIXED CODE ###

n=int(input())
arr=input()
prod=1
k=1;
l=list(map(int,arr.split(' ')))
#l.sort()

for x in l:
    if(x==0):
        k=0
        break

if(k==0):
    print(0)
else:
    for x in l:
        prod*=x
        if(prod>1000000000000000000):
            prod=-1
            break
    print(prod)
### BUGGY CODE ###

import sys

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

As.sort()
for i in range(N):
    for j in range(i + 1, N):
        if As[i] == As[j]:
            print('NO')
            sys.exit(0)
        if As[i] > As[j]:
            break

print('YES')

### FIXED CODE ###

import sys

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

As.sort()
for i in range(N):
    for j in range(i + 1, N):
        if As[i] == As[j]:
            print('NO')
            sys.exit(0)
        if As[j] > As[i]:
            break

print('YES')