There are N towns numbered 1 to N and M roads. The i-th road connects Town A_i and Town B_i bidirectionally and has a length of C_i.
Takahashi will travel between these towns by car, passing through these roads. The fuel tank of his car can contain at most L liters of fuel, and one liter of fuel is consumed for each unit distance traveled. When visiting a town while traveling, he can full the tank (or choose not to do so). Travel that results in the tank becoming empty halfway on the road cannot be done.
Process the following Q queries:
 - The tank is now full. Find the minimum number of times he needs to full his tank while traveling from Town s_i to Town t_i. If Town t_i is unreachable, print -1.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 300
 - 0 \leq M \leq \frac{N(N-1)}{2}
 - 1 \leq L \leq 10^9
 - 1 \leq A_i, B_i \leq N
 - A_i \neq B_i
 - \left(A_i, B_i\right) \neq \left(A_j, B_j\right) (if i \neq j)
 - \left(A_i, B_i\right) \neq \left(B_j, A_j\right) (if i \neq j)
 - 1 \leq C_i \leq 10^9
 - 1 \leq Q \leq N\left(N-1\right)
 - 1 \leq s_i, t_i \leq N
 - s_i \neq t_i
 - \left(s_i, t_i\right) \neq \left(s_j, t_j\right) (if i \neq j)

-----Input-----
Input is given from Standard Input in the following format:
N M L
A_1 B_1 C_1
:
A_M B_M C_M
Q
s_1 t_1
:
s_Q t_Q

-----Output-----
Print Q lines.
The i-th line should contain the minimum number of times the tank needs to be fulled while traveling from Town s_i to Town t_i. If Town t_i is unreachable, the line should contain -1 instead.

-----Sample Input-----
3 2 5
1 2 3
2 3 3
2
3 2
1 3

-----Sample Output-----
0
1

To travel from Town 3 to Town 2, we can use the second road to reach Town 2 without fueling the tank on the way.
To travel from Town 1 to Town 3, we can first use the first road to get to Town 2, full the tank, and use the second road to reach Town 3.

Difficulty: interview

Starter code:

Solutions:
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
inf = float("inf")
N, M, L = map(int, input().split())
graph = np.zeros((N, N))
for _ in range(M):
    A, B, C = map(int, input().split())
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C
shortest_paths = shortest_path(csr_matrix(graph), directed=False, method="FW")
graph = np.full((N, N), inf)
for i in range(N):
    for j in range(N):
        if shortest_paths[i][j] <= L:
            graph[i][j] = 1

Q = int(input())
def int_(num_str):
    return int(num_str) - 1

costs = shortest_path(csr_matrix(graph), directed=False, method="FW")
for _ in range(Q):
    s, t = map(int_, input().split())
    print(int(costs[s][t])-1 if costs[s][t] != inf else -1)

import numpy as np
from scipy.sparse import lil_matrix, csr_matrix
from scipy.sparse.csgraph import shortest_path

n,m,limit=map(int,input().split())
G=np.zeros((n,n),dtype=np.int64)
for i in range(m):
    a,b,cost=map(int,input().split())
    G[a-1,b-1]=cost
    G[b-1,a-1]=cost
G=shortest_path(G,method='FW')
for c in range(n):
    for l in range(n):
        if G[c][l]<=limit:
            G[c][l]=1
        else:
            G[c][l]=0
G=shortest_path(G,method='FW')
q=int(input())
Q=[map(int,input().split())for i in range(q)]
for a,b in Q:
    print(int(G[a-1][b-1])-1 if G[a-1][b-1]<10**18 else -1)

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

N,M,L=map(int,input().split())
d=[[0 for i in range(0,N)] for i in range(0,N)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c

csr1=csr_matrix(d)

a=floyd_warshall(csr1)

d=[[0 for i in range(0,N)] for j in range(0,N)]
for i in range(0,N):
    for j in range(0,N):
        if L>=a[i][j]:
            d[i][j]=1


csr2=csr_matrix(d)

data=floyd_warshall(csr2)
ans=[]
Q=int(input())
for i in range(0,Q):
    s,t=map(int,input().split())
    if data[s-1][t-1]!=float('inf'):
        ans.append(int(data[s-1][t-1])-1)
    else:
        ans.append(-1)

for i in range(Q):
    print(ans[i])

import numpy as np
from scipy.sparse.csgraph import floyd_warshall

N, M, L = list(map(int, input().split()))
Map = np.full((N, N), 10**12, dtype='int64')
for _ in range(M):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    Map[a][b] = c
    Map[b][a] = c
Q = int(input())
Query = [tuple(map(int, input().split())) for _ in range(Q)]
graph = floyd_warshall(Map).astype('int64')
graph[graph <= L] = 1
graph[graph > L] = 10**12
A = floyd_warshall(graph).astype('int64')
for s, t in Query:
    if A[s - 1][t - 1] >= 10**12:
        print((-1))
    else:
        print((int(A[s - 1][t - 1] - 1)))


import sys
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall, shortest_path

input = sys.stdin.readline

def main():
    n, m, l = map(int, input().split())
    wf = [[0 for i in range(n)] for j in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        wf[a-1][b-1] = wf[b-1][a-1] = c
    wf = np.array(wf)
    for i in range(n):
        wf[i][i] = 0
    wf = shortest_path(wf, method='FW')
    for i in range(n):
        for j in range(n):
            if wf[i][j] <= l:
                wf[i][j] = 1
            else:
                wf[i][j] = 301
    wf = shortest_path(wf, method='FW')
    q = int(input())
    ans = [None] * q
    for i in range(q):
        s, t = map(int, input().split())
        if wf[s-1][t-1] < 301:
            ans[i] = int(wf[s-1][t-1])
        else:
            ans[i] = 0
    for i in range(q):
        print(ans[i] - 1)

def __starting_point():
    main()
__starting_point()

from scipy.sparse.csgraph import floyd_warshall
N,M,L,*X = map(int, open(0).read().split())
ls = X[:3*M]
Els = [[0]*N for i in range(N)]
Q = X[3*M]
query = X[3*M+1:]
for a,b,c in zip(*[iter(ls)]*3):
  if c<=L:
    Els[a-1][b-1] = c
    Els[b-1][a-1] = c
dist = floyd_warshall(Els)
      
Els2 = [[1 if dist[i][j]<=L else 0 for j in range(N)] for i in range(N)]
ans = floyd_warshall(Els2)

for s,t in zip(*[iter(query)]*2):
  if ans[s-1][t-1]==float('inf'):
    print(-1)
    continue
  print(int(ans[s-1][t-1])-1)

# -*- coding: utf-8 -*-
"""
E - Travel by Car
https://atcoder.jp/contests/abc143/tasks/abc143_e

"""
import sys


from scipy.sparse.csgraph import floyd_warshall

def main(args):
    N, M, L = list(map(int, input().split()))
    g1 = [[float('inf')] * (N+1) for _ in range(N+1)]
    for i in range(N+1):
        g1[i][i] = 0
    for _ in range(M):
        A, B, C = list(map(int, input().split()))
        g1[A][B] = g1[B][A] = C
    d1 = floyd_warshall(g1)
    g2 = [[float('inf')] * (N+1) for _ in range(N+1)]
    for i in range(N+1):
        for j in range(N+1):
            if i == j:
                g2[i][j] = 0
            elif d1[i][j] <= L:
                g2[i][j] = g2[j][i] = 1
    d2 = floyd_warshall(g2)
    Q = int(input())
    for _ in range(Q):
        s, t = list(map(int, input().split()))
        print((-1 if d2[s][t] == float('inf') else int(d2[s][t]) - 1))


def __starting_point():
    main(sys.argv[1:])

__starting_point()

# scipy使う場合
import sys
input = sys.stdin.readline
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

n,m,l = list(map(int,input().split()))

# m行の入力から距離を値に持つ隣接行列を作成 0-indexed
# directed:無向グラフならFalse、有向グラフならTrue
def make_d_matrix(n,m,directed=False):
    inf = 10**13
    d = [[inf] * n for _ in range(n)]
    if(directed):
        for _ in range(m):
            a,b,c = list(map(int, input().split()))
            d[a-1][b-1] = c
    else:
        for _ in range(m):
            a,b,c = list(map(int, input().split()))
            d[a-1][b-1] = c
            d[b-1][a-1] = c
    return d

d = make_d_matrix(n,m)
csr_graph = csr_matrix(d)
d1 = floyd_warshall(csr_graph,directed=False)

inf = 10**3
for i in range(n):
    for j in range(n):
        d1[i][j] = 1 if (d1[i][j] <= l) else inf

csr_graph = csr_matrix(d1)
d2 = floyd_warshall(csr_graph,directed=False)

q = int(input())

for _ in range(q):
    s,t = list(map(int, input().split()))
    tmp = d2[s-1][t-1]
    if(tmp >= inf):
        print((-1))
    else:
        print((int(tmp-1)))


import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
ii0 = lambda: ii() - 1
mis = lambda: list(map(int, input().split()))
lmis = lambda: list(mis())
INF = float('inf')

def main():
    N,M,L = mis()
    from scipy.sparse.csgraph import floyd_warshall
    import numpy as np
    INF = np.iinfo(np.int64).max
    d = np.full((N,N), INF, dtype=np.uint64)
    for i in range(N):
        d[i,i] = 0
    #
    for _ in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        if c <= L:
            d[a,b] = c
            d[b,a] = c
    #
    '''
    for k in range(N):
        for i in range(N):
            np.minimum(d[i,:], d[i,k]+d[k,:], out=d[i,:])    
    '''
    d = floyd_warshall(d)
    #
    d2 = np.full((N,N), INF, dtype=np.uint64)
    for i in range(N):
        d2[i, i] = 0
    for i in range(N):
        for j in range(N):
            if d[i, j] <= L:
                d2[i, j] = 1
    #
    '''
    for k in range(N):
        for i in range(N):
            np.minimum(d2[i,:], d2[i,k]+d2[k,:], out=d2[i,:])    
    '''
    d2 = floyd_warshall(d2)
    #
    Q = ii()
    for _ in range(Q):
        s,t = mis()
        s -= 1
        t -= 1
        dist = d2[s,t]
        if dist == INF:
            print((-1))
        else:
            print((int(dist)-1))




main()


MOD = 10 **9 + 7
INF = 10 ** 10
import numpy as np
from  scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

def main():
    n,m,l = map(int,input().split())
    dist = [[INF] * n for _ in range(n)]  
    for _ in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        dist[a][b] = c
        dist[b][a] = c

    csr = csr_matrix(dist)
    dist1 = floyd_warshall(csr)
    dist1 = np.where(dist1 <= l,1,INF)
    cnt = floyd_warshall(dist1)
    q = int(input())
    for _ in range(q):
        s,t = map(int,input().split())
        s -= 1
        t -= 1
        print(-1 if cnt[s][t] == INF  else int(cnt[s][t]) - 1)
def __starting_point():
    main()
__starting_point()

def resolve():
    from scipy.sparse.csgraph import floyd_warshall
    import numpy as np
    import sys
    input = sys.stdin.readline
    n, m, l = list(map(int, input().split()))
    inf = 10 ** 20
    ar = [[0] * n for _ in range(n)]
    for _ in range(m):
        a, b, c = list(map(int, input().split()))
        ar[a - 1][b - 1] = c
        ar[b - 1][a - 1] = c
    x = floyd_warshall(ar)
    br = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if x[i, j] <= l:
                br[i][j] = 1
                br[j][i] = 1
    y = floyd_warshall(br)
    q = int(input())
    for _ in range(q):
        s, t = list(map(int, input().split()))
        p = y[s - 1, t - 1]
        print((int(p) - 1 if p < inf else -1))


def __starting_point():
    resolve()

__starting_point()

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import sys
def input():
	return sys.stdin.readline()[:-1]

n, m, l = map(int, input().split())
dist = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
	a, b, c = map(int, input().split())
	dist[a-1][b-1] = c
	dist[b-1][a-1] = c

fw = floyd_warshall(csr_matrix(dist))

num = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
	for j in range(n):
		if fw[i][j] <= l:
			num[i][j] = 1

ans = floyd_warshall(csr_matrix(num))

q = int(input())
for _ in range(q):
	s, t = map(int, input().split())
	if ans[s-1][t-1] > n:
		print(-1)
	else:
		print(int(ans[s-1][t-1])-1)

from scipy.sparse.csgraph import floyd_warshall

N, M, L = list(map(int, input().split()))
edges = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b, c = list(map(int, input().split()))
    edges[a - 1][b - 1] = c
    edges[b - 1][a - 1] = c

Q = int(input())
st = []
for _ in range(Q):
    st.append([int(j) - 1 for j in input().split()])

edges = floyd_warshall(edges)

for i in range(N):
    for j in range(N):
        if edges[i][j] <= L:
            edges[i][j] = 1
        else:
            edges[i][j] = 0

edges = floyd_warshall(edges)

for i, j in st:
    if edges[i][j] == float("inf"):
        print((-1))
    else:
        print((int(edges[i][j]) - 1))


#!/usr/bin/env python3
import sys


def solve(N: int, M: int, L: int, A: "List[int]", B: "List[int]", C: "List[int]", Q: int, s: "List[int]", t: "List[int]"):
    import numpy as np    
    from scipy.sparse import coo_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    from itertools import filterfalse
    # coo_matrix((data, (i, j)), [shape=(M, N)])
    mat = floyd_warshall(coo_matrix((C, (A, B)), shape=(N+1, N+1), dtype=np.int32).tocsr(), directed=False)
    mat = floyd_warshall(mat <= L, directed=False)
    for ss, tt in zip(s, t):
        yield -1 if np.isinf(mat[ss][tt]) else int(mat[ss][tt]) - 1


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    s = [int()] * (Q)  # type: "List[int]"
    t = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        s[i] = int(next(tokens))
        t[i] = int(next(tokens))
    print(*solve(N, M, L, A, B, C, Q, s, t), sep="\n")

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    #test()
    main()

__starting_point()

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, L: int, A: "List[int]", B: "List[int]", C: "List[int]", Q: int, s: "List[int]", t: "List[int]"):
    import numpy as np    
    from scipy.sparse import coo_matrix    
    from scipy.sparse.csgraph import floyd_warshall
   # coo_matrix((data, (i, j)), [shape=(M, N)])
    mat = floyd_warshall(coo_matrix((C, (A, B)), shape=(N+1, N+1), dtype=np.int32).tocsr(), directed=False)
    mat = floyd_warshall(mat <= L, directed=False)
    for ss, tt in zip(s, t):
        yield -1 if np.isinf(mat[ss][tt]) else int(mat[ss][tt]) - 1


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    s = [int()] * (Q)  # type: "List[int]"
    t = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        s[i] = int(next(tokens))
        t[i] = int(next(tokens))
    print(*solve(N, M, L, A, B, C, Q, s, t), sep="\n")

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    #test()
    main()

__starting_point()

import sys
from heapq import heappop, heappush
from scipy.sparse.csgraph import floyd_warshall
input = sys.stdin.readline
 
def main():
    n,w,l = map(int,input().split())
    d = [[10**15 for _ in range(n)] for _ in range(n)]
    for _ in range(w):
        x,y,z = map(int,input().split())
        x -= 1
        y -= 1
        if z > l:
            continue
        d[x][y] = z
        d[y][x] = z
    for i in range(n):
        d[i][i] = 0
    d = floyd_warshall(d)
    G = [[10**15 for _ in range(n)] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            if d[i][j] <= l:
                G[i][j] = 1
                G[j][i] = 1
    for i in range(n):
        G[i][i] = 0
    G = floyd_warshall(G)
    q = int(input())
    for _ in range(q):
        s,t = map(int,input().split())
        s -= 1
        t -= 1
        ans = G[s][t]
        if ans == 10**15:
            print(-1)
            continue
        print(int(ans)-1)
    
def __starting_point():
    main()
__starting_point()

import numpy as np
from scipy.sparse.csgraph import floyd_warshall


def main():
    N, M, L = map(int, input().split())
    graph = [[0] * N for _ in range(N)]
    for _ in range(M):
        s, t, w = map(int, input().split())
        if w <= L:
            graph[s-1][t-1] = graph[t-1][s-1] = w
    graph = floyd_warshall(graph, directed=False)
    graph = floyd_warshall(graph <= L, directed=False)
    graph[np.isinf(graph)] = 0

    Q = int(input())
    ans = []
    for _ in range(Q):
        s, t = map(int, input().split())
        ans.append(int(graph[s-1][t-1]) - 1)
    print(*ans, sep='\n')


def __starting_point():
    main()

__starting_point()

import sys
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

input = sys.stdin.readline

cost = []
row = []
col = []

n, m, l = list(map(int, input().split()))

for _ in range(m):
    a, b, c = list(map(int, input().split()))
    cost.append(c)
    row.append(a-1)
    col.append(b-1)

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

csr = csr_matrix((cost, (row, col)), shape = (n, n))
path = floyd_warshall(csr, directed=False)

cost = []
row = []
col = []

for i in range(n):
    for j in range(n):
        if path[i][j] <= l:
            cost.append(1)
            row.append(i)
            col.append(j) 

csr = csr_matrix((cost, (row, col)), shape = (n, n))
path = floyd_warshall(csr, directed=False)

INF = float('inf')

for s,t in st:
    ans = path[s-1][t-1]
    if ans == INF:
        print((-1))
    else:
        print((int(ans) - 1))






import sys
input = sys.stdin.readline

n,m,l = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
q = int(input())
S = [list(map(int,input().split())) for i in range(q)]

from scipy.sparse.csgraph import floyd_warshall

for i in range(m):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        A[i][j] -= 1

for i in range(q):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        S[i][j] -= 1

M = [[float("inf")] * n for i in range(n)]

for i in range(n):
    M[i][i] = 0

for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             M[i][j] = min(M[i][j], M[i][k] + M[k][j])

M = floyd_warshall(M)

for i in range(n):
    for j in range(n):
        M[i][j] = 1 if M[i][j] <= l else float("inf")

for i in range(n):
    M[i][i] = 0

# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             M[i][j] = min(M[i][j], M[i][k] + M[k][j])

M = floyd_warshall(M)

for i in range(q):
    ans = M[S[i][0]][S[i][1]]-1
    if ans == float("inf"):
        ans = -1
    print(int(ans))

# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import floyd_warshall

"""
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
"""
N, M, L = map(int, input().split())

d = [[0 for i in range(N)] for i in range(N)]

for i in range(M):
    A, B, C = map(int, input().split())
    d[A-1][B-1] = C
    d[B-1][A-1] = C

d = floyd_warshall(d, directed = False)
S = [[0 for i in range(N)] for i in range(N)]


for i in range(N):
    for j in range(N):
        if d[i][j] <= L:
            S[i][j] = 1
            S[j][i] = 1
            
S = floyd_warshall(S, directed = False)

Q = int(input())

for i in range(Q):
    s, t = map(int, input().split())
    if S[s-1][t-1] == float("inf"):
        print(-1)
    else: 
        print(int(S[s-1][t-1]-1))

# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import floyd_warshall

N, M, L = map(int,input().split())
  
d = [[0 for i in range(N)] for j in range(N)] 
for i in range(M):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(N):
    d[i][i] = 0

d = floyd_warshall(d, directed = False)
LN = [[0 for i in range(N)] for j in range(N)]

for i in range(N):
    for j in range(N):
        if d[i][j] <= L:
            LN[i][j] = 1
            LN[j][i] = 1

LN = floyd_warshall(LN, directed = False)    
s = []
t = []
Q = int(input())
for i in range(Q):
    s1, t1 = map(int,input().split())
    s.append(s1)
    t.append(t1)
for i in range(Q):
    if LN[s[i]-1][t[i]-1] == float("inf"):
        print(-1)
    else:
        print(int(LN[s[i]-1][t[i]-1]-1))

from scipy.sparse.csgraph import floyd_warshall

# ダイクストラではなくワーシャルフロイドで解く
N, M, L = list(map(int, input().split()))
# graph = [[] for _ in range(N)]
distant = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = list(map(int, input().split()))
    a, b = a-1, b-1
    if c > L:
        continue
    distant[a][b] = c
    distant[b][a] = c

distant = floyd_warshall(distant)
another = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if distant[i][j] <= L:  # 行けるところまでいくという印象
            another[i][j] = 1
another = floyd_warshall(another)
Q = int(input())
for _ in range(Q):
    s, t = [int(x)-1 for x in input().split()]
    if another[s][t] == float('inf'):
        print((-1))
        continue
    print((int(another[s][t])-1))
    # if distant[s][t] == float('inf'):
    #     print(-1)
    #     continue
    # print(int(distant[s][t])//L + min(1, int(distant[s][t]) % L) - 1)
# 燃料が4で
# 1 -> 4 -> 2
# のとき、距離は7だから一見すると補給回数は1で良さそうだけど、実は2回必要
# 今、２点間の最小距離を求めておいて、もう一つのグラフは「最短距離がL以下の2点に辺(重み1)を張る」


import numpy as np
import sys
from scipy.sparse.csgraph import floyd_warshall,csgraph_from_dense
from scipy.sparse import csr_matrix
input = sys.stdin.readline
def inputs():return [int(x) for x in input().split()]
N,M,L = inputs()
ABC =[inputs() for _ in range(M)]
graph = [[10**13]*(N+1) for _ in range(N+1)]
for a,b,c in ABC:
    graph[a][b] = c
G = csgraph_from_dense(graph, null_value=10**13)
dist_mat = floyd_warshall(graph,directed=False)
graph2 = np.array([[10**13]*(N+1) for _ in range(N+1)])
np.fill_diagonal(graph2,0)
graph2[dist_mat<=L]=1
dist_mat2 = floyd_warshall(graph2,directed=False)
dist_mat2[dist_mat2==10**13]=0
Q = int(input())
for i in range(Q):
    s,t = inputs()
    print((int(dist_mat2[s,t])-1))



from scipy.sparse.csgraph import floyd_warshall

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

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

# neighborhood graph
nei_graph = [[0] * N for _ in range(N)]
for a, b, c in G:
    nei_graph[a - 1][b - 1] = c
    nei_graph[b - 1][a - 1] = c

# Warshall Floyd
nei_graph = floyd_warshall(nei_graph)

# 1 if distance is less than L
for i in range(N):
    for j in range(N):
        if nei_graph[i][j] <= L:
            nei_graph[i][j] = 1
        else:
            nei_graph[i][j] = 0

nei_graph = floyd_warshall(nei_graph)

for start, end in Query:
    if nei_graph[start - 1][end - 1] - 1 == float('inf'):
        print(-1)
    else:
        print(int(nei_graph[start - 1][end - 1] - 1))

import numpy as np
from scipy.sparse.csgraph import floyd_warshall

N,M,L = map(int,input().split())
gurahu = np.zeros((N,N))

for k in range(M):
    a,b,c = map(int,input().split())
    gurahu[a-1,b-1] = c
    gurahu[b-1,a-1] = c

gurahu = floyd_warshall(gurahu, directed=False)
gurahu = np.where((gurahu <= L) & (gurahu > 0), 1, 0)
gurahu = floyd_warshall(gurahu) - np.ones((N, N))

Q = int(input())

for k in range(Q):
    s,t = map(int,input().split())
    ans = gurahu[s-1,t-1]
    if ans == float('inf'):
        print(-1)
    else:
        print(int(ans))

3
# -*- coding: utf-8 -*-

# scipy version

import sys
from collections import deque
from array import array

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

def input():
    return sys.stdin.readline().rstrip('\n')

##### main

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

C = [[0]*N for _ in range(N)]

for i in range(M):
    a,b,c = list(map(int, input().split()))
    if c>L:
        continue
    C[a-1][b-1] = c

Q = int(input())

ST = [None]*Q

for i in range(Q):
    s, t = list(map(int, input().split()))
    ST[i] = (s-1,t-1)

dist_matrix, predecessors = floyd_warshall(csgraph=C, directed=False, return_predecessors=True)

# D[i][j] <= L となる i,j に辺を張る
for i in range(N):
    for j in range(i+1,N):
        if dist_matrix[i][j] <= L:
            C[i][j] = 1

dist_matrix, predecessors = floyd_warshall(csgraph=C, directed=False, return_predecessors=True)

# answer
for q in range(Q):
    i,j = ST[q]
    step = dist_matrix[i][j]
    if step > 10**9:
        print((-1))
    else:
        print((int(step-1)))


from scipy.sparse.csgraph import dijkstra as di

n,m,l = list(map(int, input().split()))

inf = float('INF')
road = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a,b,c = list(map(int, input().split()))
    a -= 1
    b -= 1
    road[a][b] = road[b][a] = c

def warshall(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]

roads = di(road, n)
# [print(cost) for cost in road]
# print()
costs = [[1 if roads[i][j] <= l and i != j else 0 for j in range(n)] for i in range(n)]
costs = di(costs, n)

# [print(cost) for cost in costs]
q = int(input())
for i in range(q):
    s,t = list(map(int, input().split()))
    
    print((int(costs[s-1][t-1]-1) if costs[s-1][t-1] < inf else -1))


import numpy as np
from scipy.sparse.csgraph import floyd_warshall

N,M,L=list(map(int,input().split()))
INF = 1 << 31
dist=np.array([[INF for _ in range(N)] for _ in range(N)])

for i in range(N):
  dist[i][i]=0
  
for i in range(M):
  a,b,c=list(map(int,input().split()))
  a-=1
  b-=1
  dist[a][b]=c
  dist[b][a]=c

dist = floyd_warshall(dist)

for i in range(N):
  for j in range(N):
    if dist[i][j]<=L:
      dist[i][j]=1
    else:
      dist[i][j]=INF

dist = floyd_warshall(dist)
dist[dist==INF]=0
#dist=dist.astype(int)
#print(dist)

Q=int(input())
ans=[0]*Q
for q in range(Q):
  s,t=list(map(int,input().split()))
  s-=1
  t-=1
  ans[q]=int(dist[s][t]-1)

for a in ans:
  print((-1 if a==INF else a))



def resolve():
    from scipy.sparse.csgraph import floyd_warshall
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, m, l = list(map(int, input().split()))
    inf = float("inf")
    ar = [[0] * n for _ in range(n)]
    for _ in range(m):
        a, b, c = list(map(int, input().split()))
        ar[a - 1][b - 1] = c
    x = floyd_warshall(ar, directed=False)
    br = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if x[i, j] <= l:
                br[i][j] = 1
    y = floyd_warshall(br, directed=False)
    q = int(input())
    for _ in range(q):
        s, t = list(map(int, input().split()))
        print((int(y[s - 1, t - 1]) - 1 if y[s - 1, t - 1] < inf else -1))


def __starting_point():
    resolve()

__starting_point()

import sys
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall, csgraph_to_dense
from scipy.sparse import issparse
sys.setrecursionlimit(10**7)

n, m, l = [int(i) for i in sys.stdin.readline().split()]
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c

res = floyd_warshall(csgraph_from_dense(graph))
if issparse(res):
    res = csgraph_to_dense(res)
res = np.where(res <= l, 1, 0)
new_res = floyd_warshall(res)
new_res[new_res == np.inf] = 0
q = int(input())
for j in range(q):
    s, t = [int(i) for i in sys.stdin.readline().split()]
    s -= 1
    t -= 1
    dis = new_res[s, t]
    print(int(dis) - 1)

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

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

start = []
goal = []
cost = []
for _ in range(M):
    A, B, C = list(map(int, input().split()))
    A -= 1
    B -= 1
    start.append(A)
    goal.append(B)
    cost.append(C)
    start.append(B)
    goal.append(A)
    cost.append(C)

graph = csr_matrix((cost, (start, goal)), shape = (N, N))
can_reach_with_L = dijkstra(graph, directed = False, limit = L)
ans = dijkstra(can_reach_with_L, directed = False, unweighted = True)

Q = int(input())
for _ in range(Q):
    s, t = list(map(int, input().split()))
    s -= 1
    t -= 1
    if ans[s][t] == float('inf'):
        print((-1))
    else:
        print((int(ans[s][t] + 0.5) - 1))


from scipy.sparse.csgraph import floyd_warshall
 
# 下準備
N, M, L = map(int,input().split())
d = [[float("inf") for i in range(N)] for j in range(N)]
answer_d = [[float("inf") for i in range(N)] for j in range(N)]
for i in range(M):
    A, B, C = map(int,input().split())
    d[A-1][B-1] = d[B-1][A-1] = C
for i in range(N):
    d[i][i] = 0
 
# 燃料補給回数の最小値を求める
d = floyd_warshall(d)
for i in range(N):
    for j in range(N):
        if d[i][j] <= L:
            answer_d[i][j] = answer_d[j][i] = 1
d = floyd_warshall(answer_d)
 
# クエリを答える
Q = int(input())
answer = [-1]*Q
for i in range(Q):
    s, t = map(int,input().split())
    if d[s-1][t-1] != float("inf"):
        answer[i] = d[s-1][t-1]-1
 
for i in answer:
    print(i)

import sys
from scipy.sparse.csgraph import floyd_warshall

N, M, L = map(int, input().split())
INF = 10 **9 +1
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  a, b, = a - 1, b -1
  G[a][b] = c
  G[b][a] = c

#全点間最短距離を計算
G = floyd_warshall(G)


#コストL以下で移動可能な頂点間のコスト1の辺を張る
E = [[float('inf')] * N for i in range(N)]
for i in range(N):
  for j in range(N):
    if G[i][j] <= L:
      E[i][j] = 1

#全点間最短距離を計算
E = floyd_warshall(E)

#クエリに答えていく
Q = int(input())
for i in range(Q):
  s, t = map(int, input().split())
  s, t = s - 1, t-1
  print(int(E[s][t] - 1) if E[s][t] != float('inf') else -1)

MOD = 10 **9 + 7
INF = 10 ** 10
import numpy as np
from  scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

def main():
    n,m,l = map(int,input().split())
    dist = [[np.inf] * n for _ in range(n)]  
    for _ in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        dist[a][b] = c
        dist[b][a] = c

    csr = csr_matrix(dist)
    dist1 = floyd_warshall(csr,directed = False)
    dist1 = np.where(dist1 <= l,1,np.inf)
    cnt = floyd_warshall(dist1,directed = False)
    cnt[cnt == np.inf] = 0
    cnt = cnt.astype(int)
    q = int(input())
    for _ in range(q):
        s,t = map(int,input().split())
        s -= 1
        t -= 1
        print(cnt[s][t] - 1)
def __starting_point():
    main()
__starting_point()

def resolve():
    from scipy.sparse.csgraph import floyd_warshall
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, m, l = list(map(int, input().split()))
    inf = 10 ** 20
    ar = [[0] * n for _ in range(n)]
    for _ in range(m):
        a, b, c = list(map(int, input().split()))
        ar[a - 1][b - 1] = c
    x = floyd_warshall(ar, directed=False)
    br = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if x[i, j] <= l:
                br[i][j] = 1
    y = floyd_warshall(br, directed=False)
    q = int(input())
    for _ in range(q):
        s, t = list(map(int, input().split()))
        p = y[s - 1, t - 1]
        print((int(y[s - 1, t - 1]) - 1 if y[s - 1, t - 1] < inf else -1))


def __starting_point():
    resolve()

__starting_point()

# import numpy as np
from scipy.sparse.csgraph import floyd_warshall
N, M, L = map(int, input().split())

INF = 10 ** 18
dist1 = [[INF] * N for _ in range(N)]
for i in range(N):
    dist1[i][i] = 0

for _ in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    dist1[A][B] = C
    dist1[B][A] = C

dist1 = floyd_warshall(dist1)

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

dist2 = floyd_warshall(dist2)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    if dist2[s][t] >= INF:
        print (-1)
    else:
        print (int(dist2[s][t] - 1))

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

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

adjacency_matrix = np.zeros((n, n))
for a, b, c in abc:
    adjacency_matrix[a-1, b-1] = c
    adjacency_matrix[b-1, a-1] = c

shotest = dijkstra(adjacency_matrix)
fuel_once = np.where(shotest <= l, 1, 0)
fuel_times = dijkstra(fuel_once-np.eye(n))

for s, t in st:
    ans = fuel_times[s-1][t-1]
    if np.isinf(ans):
        print((-1))
    else:
        print((int(ans) - 1))


from scipy.sparse.csgraph import floyd_warshall
import numpy as np

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

D = np.ones([N, N]) * np.inf
D[np.eye(N, dtype=bool)] = 0

for _ in range(M):
  A, B, C = map(int, input().split())
  D[A-1, B-1] = C
  D[B-1, A-1] = C

D = floyd_warshall(D)
D2 = (D<=L)*1.0 # boolean -> float
D2[D2==0] = np.inf
# D2 = (D <= L) + (D > L)*np.inf

D2 = floyd_warshall(D2) - 1

Q = int(input())
for _ in range(Q):
  s, t = map(int, input().split())
  r = D2[s-1, t-1]
  if r < np.inf:
    print(int(r))
  else:
    print(-1)

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n, m, l = map(int, input().split())
INF = 1 << 60

dist = [[INF] * n for _ in range(n)]

for i in range(n):
    dist[i][i] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if c > l:
        continue
    dist[a][b] = c
    dist[b][a] = c


dist = floyd_warshall(csr_matrix(dist))

dist2 = np.full_like(dist, 1)
dist2[np.where(dist > l)] = INF
dist2 = floyd_warshall(dist2, directed=False)
dist2[dist2 == INF] = 0
dist2 = dist2.astype(int)

q = int(input())

ans = []
for _ in range(q):
    s, t = map(int, input().split())
    if dist[s - 1, t - 1] == -1:
        ans.append(-1)
    else:
        ans.append(dist2[s - 1, t - 1] - 1)

print(*ans, sep="\n")

import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

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

d=[[sys.maxsize]*(n) for _ in range(n)]
e=[[sys.maxsize]*(n) for _ in range(n)]
for i in range(n):
  d[i][i] = 0
  e[i][i] = 0

for _ in range(m):
  a,b,c = map(int, input().split())
  d[a-1][b-1]=c
  d[b-1][a-1]=c

d=floyd_warshall(csr_matrix(d))
for i in range(n):
  for j in range(n):
    if d[i][j] <= l:
      e[i][j] = 1

e=floyd_warshall(csr_matrix(e))

q=int(input())
for _ in range(q):
  s,t = map(int, input().split())
  if e[s-1][t-1] == sys.maxsize:
    print(-1)
  else:
    print(int(e[s-1][t-1]-1))

import sys
from scipy.sparse.csgraph import floyd_warshall
N, M, L = list(map(int, input().split()))
INF = 10 ** 9 + 1
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
    a, b, c = list(map(int, sys.stdin.readline().split()))
    a, b = a - 1, b - 1
    G[a][b] = c
    G[b][a] = c


# 全点間最短距離を計算
G = floyd_warshall(G)


# コストL以下で移動可能な頂点間にコスト１の辺を張る
E = [[float('inf')] * N for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j] <= L:
            E[i][j] = 1


# そのグラフの全点間最短距離を求める
E = floyd_warshall(E)


# クエリに答えていく
Q = int(input())
for i in range(Q):
    s, t = list(map(int, sys.stdin.readline().split()))
    s, t = s - 1, t - 1
    print((int(E[s][t] - 1) if E[s][t] != float('inf') else - 1))


import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
INF = 10**12
N, M, L = map(int, input().split())

A = []; B = []; C = []
for i in range(M):
    a, b, c = map(int, input().split())
    A.append(a - 1); B.append(b - 1); C.append(c)
A = np.array(A); B = np.array(B); C = np.array(C)

graph = csr_matrix((C, (A, B)), (N, N))
d = floyd_warshall(graph, directed=False)

d[d <= L] = 1
d[d > L] = INF

d = floyd_warshall(d, directed=False)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    if d[s - 1][t - 1] != INF:
        print(int(d[s - 1][t - 1]) - 1)
    else:
        print(- 1)

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n, m, l = map(int, input().split())
INF = 1 << 60

dist = [[INF] * n for _ in range(n)]

for i in range(n):
    dist[i][i] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if c > l:
        continue
    dist[a][b] = c
    dist[b][a] = c


dist = floyd_warshall(csr_matrix(dist))

dist2 = np.full_like(dist, 1)
dist2[np.where(dist > l)] = INF
dist2 = floyd_warshall(dist2, directed=False)
dist2[dist2 == INF] = 0
dist2 = dist2.astype(int)

q = int(input())

ans = []
for _ in range(q):
    s, t = map(int, input().split())
    ans.append(dist2[s - 1, t - 1] - 1)

print(*ans, sep="\n")

from scipy.sparse.csgraph import floyd_warshall
import numpy as np

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

D = np.ones([N, N]) * np.inf
D[np.eye(N, dtype=bool)] = 0

for _ in range(M):
  A, B, C = list(map(int, input().split()))
  D[A-1, B-1] = C
  D[B-1, A-1] = C

D = floyd_warshall(D)
D2 = D <= L

D2 = floyd_warshall(D2)

Q = int(input())
for _ in range(Q):
  s, t = list(map(int, input().split()))
  r = D2[s-1, t-1] - 1
  if r < np.inf:
    print((int(r)))
  else:
    print((-1))



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))

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

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

start = []
goal = []
cost = []
for _ in range(M):
    A, B, C = list(map(int, input().split()))
    A -= 1
    B -= 1
    start.append(A)
    goal.append(B)
    cost.append(C)
    start.append(B)
    goal.append(A)
    cost.append(C)

graph = csr_matrix((cost, (start, goal)), shape = (N, N))
can_reach_with_L = floyd_warshall(graph, directed = False)
can_reach_with_L[can_reach_with_L > L] = 0
ans = floyd_warshall(can_reach_with_L, directed = False, unweighted = True)

Q = int(input())
for _ in range(Q):
    s, t = list(map(int, input().split()))
    s -= 1
    t -= 1
    if ans[s][t] == float('inf'):
        print((-1))
    else:
        print((int(ans[s][t] + 0.5) - 1))


from scipy.sparse.csgraph import floyd_warshall

N,M,L = map(int,input().split())
abc = [[int(i) for i in input().split()] for j in range(M)]
Q = int(input())
st = [[int(i) for i in input().split()] for j in range(Q)]
INF = 1<<30
Path = [[INF for i in range(N)] for j in range(N)]
AnsPath = [[INF for i in range(N)] for j in range(N)]

def PathInit():
    for i in range(N):
        Path[i][i] = 0

PathInit()
for i,j,k in abc:
    Path[i-1][j-1] = k
    #双方向
    Path[j-1][i-1] = k

Path = floyd_warshall(Path)

for i in range(N):
    for j in range(N):
        if Path[i][j] <= L:
            AnsPath[i][j] = 1
AnsPath = floyd_warshall(AnsPath)
for s,t in st:
    if AnsPath[s-1][t-1] == INF:
        print(-1)
    else:
        print(int(AnsPath[s-1][t-1]-1))

def resolve():
    from scipy.sparse.csgraph import floyd_warshall
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, m, l = list(map(int, input().split()))
    inf = 10 ** 20
    ar = [[0] * n for _ in range(n)]
    for _ in range(m):
        a, b, c = list(map(int, input().split()))
        ar[a - 1][b - 1] = c
    x = floyd_warshall(ar, directed=False)
    br = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if x[i, j] <= l:
                br[i][j] = 1
    y = floyd_warshall(br, directed=False)
    q = int(input())
    for _ in range(q):
        s, t = list(map(int, input().split()))
        print((int(y[s - 1, t - 1]) - 1 if y[s - 1, t - 1] < inf else -1))


def __starting_point():
    resolve()

__starting_point()

import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

N, M, L = inpl()
graph = [[0]*N for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        graph[A-1][B-1] = C

Q = int(input())
ST = []
for _ in range(Q):
    s, t = inpl()
    s -= 1
    t -= 1
    ST.append((s, t))

distance = floyd_warshall(csr_matrix(graph), directed=False)
path = [[0]*N for _ in range(N)]
for i in range(N-1):
    for j in range(i+1,N):
        d = distance[i][j]
        if d <= L:
            path[i][j] = 1
ans = floyd_warshall(csr_matrix(path), directed=False)
for s, t in ST:
    if ans[s][t] == np.float('inf'):
        print((-1))
    else:
        print((int(ans[s][t]-1)))


#!/usr/bin/env python3
import sys


def solve(N: int, M: int, L: int, A: "List[int]", B: "List[int]", C: "List[int]", Q: int, s: "List[int]", t: "List[int]"):
    import numpy as np    
    from scipy.sparse import coo_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    mat = floyd_warshall(coo_matrix((C, (A, B)), shape=(N+1, N+1), dtype=np.int32).tocsr(), directed=False)
    mat = floyd_warshall(mat <= L, directed=False)
    for ss, tt in zip(s, t):
        yield -1 if np.isinf(mat[ss][tt]) else int(mat[ss][tt]) - 1


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    s = [int()] * (Q)  # type: "List[int]"
    t = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        s[i] = int(next(tokens))
        t[i] = int(next(tokens))
    print(*solve(N, M, L, A, B, C, Q, s, t), sep="\n")

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    #test()
    main()

__starting_point()

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
n, m, l = map(int, input().split())
F = np.zeros((n, n))
for _ in range(m):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  F[a, b] = c
  F[b, a] = c
csr = csr_matrix(F)
A = floyd_warshall(csr)
G = np.zeros((n, n))
for i in range(n-1):
  for j in range(i+1, n):
    if A[i][j] <= l:
      G[i, j] = 1
      G[j, i] = 1
ncsr = csr_matrix(G)
B =  floyd_warshall(ncsr)
q = int(input())
for _ in range(q):
  s, t = map(int, input().split())
  k = B[s-1][t-1]
  if k == float("inf"):
    print(-1)
  else:
    print(int(k)-1)

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import csgraph_from_dense

INF = float('inf')

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

    # G[x][y]: xからyへ直接移動するときのコスト。移動できない場合はINF
    G = [[INF] * (N+1) for n in range(N+1)]

    for i in range(M):
        a, b, c = map(int, input().split())
        G[a][b] = c
        G[b][a] = c
    G = csgraph_from_dense(G, null_value=INF)

    Q = int(input())
    Queries = []
    for i in range(Q):
        s, t = map(int, input().split())
        Queries.append((s, t))

    # ワーシャルフロイド法で、全点間の距離を求める
    cost = floyd_warshall(G)
    # 全点間の距離のうち、移動距離がL以内でおさまる頂点同士は、給油せずにすむ
    # そこで、全点間の距離のうち、移動距離がL以内でおさまる頂点同士を距離1で結んだグラフを作成し、
    # そのグラフに対してワーシャルフロイド法で最短距離を計算することで、
    # refuel[x][y] =「xからyへ移動するときの給油回数+1」というグラフを作成できる
    no_refuel = [[1 if x <= L else INF for x in c] for c in cost]
    no_refuel = csgraph_from_dense(no_refuel, null_value=INF)
    refuel_count = floyd_warshall(no_refuel)

    ans = []
    for s, t in Queries:
        d = refuel_count[s][t]
        ans.append(int(d-1) if d != INF else -1)
    
    print(*ans, sep='\n')

def __starting_point():
    main()
__starting_point()

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
inf = float("inf")
N, M, L = map(int, input().split())
graph = np.zeros((N, N))
for _ in range(M):
    A, B, C = map(int, input().split())
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C
shortest_paths = shortest_path(csr_matrix(graph), directed=False, method="D")
graph = np.full((N, N), inf)
for i in range(N):
    for j in range(N):
        if shortest_paths[i][j] <= L:
            graph[i][j] = 1

Q = int(input())
def int_(num_str):
    return int(num_str) - 1

costs = shortest_path(csr_matrix(graph), directed=False, method="D")
for _ in range(Q):
    s, t = map(int_, input().split())
    print(int(costs[s][t])-1 if costs[s][t] != inf else -1)

import sys
import numpy as np
from scipy.sparse import*
F = csgraph.floyd_warshall
CSR = csr_matrix
input = sys.stdin.readline

n,m,l = map(int,input().split())
cost = [[0]*n for i in range(n)]
for i in range(m):
  a,b,c = map(int,input().split())
  cost[a-1][b-1] = c
  cost[b-1][a-1] = c  

Cost = F(CSR(cost))
Cost = F(CSR(np.where((0<Cost)&(Cost<=l),1,0)))

q = int(input())
for i in range(q):
  s,t = map(int,input().split())
  print(-1 if np.isinf(Cost[s-1][t-1]) else int(Cost[s-1][t-1])-1)

# scipy使う場合
import sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

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

# m行の入力から距離を値に持つ隣接行列を作成 0-indexed
# directed:無向グラフならFalse、有向グラフならTrue
def make_d_matrix(n,m,directed=False):
    inf = 10**13
    d = [[inf] * n for _ in range(n)]
    if(directed):
        for _ in range(m):
            a,b,c = map(int, input().split())
            d[a-1][b-1] = c
    else:
        for _ in range(m):
            a,b,c = map(int, input().split())
            d[a-1][b-1] = c
            d[b-1][a-1] = c
    return d

d = make_d_matrix(n,m)
csr_graph = csr_matrix(d)
d1 = floyd_warshall(csr_graph,directed=False)

inf = 10**3
for i in range(n):
    for j in range(n):
        d1[i][j] = 1 if (d1[i][j] <= l) else inf

csr_graph = csr_matrix(d1)
d2 = floyd_warshall(csr_graph,directed=False)

q = int(input())

for _ in range(q):
    s,t = map(int, input().split())
    tmp = d2[s-1][t-1]
    if(tmp >= inf):
        print(-1)
    else:
        print(int(tmp-1))

import numpy as np
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int,input().split())
INF = 1 << 31
dist=np.array([[INF for _ in range(N)] for _ in range(N)])

for i in range(N):
  dist[i][i]=0
  
for i in range(M):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  dist[a][b]=c
  dist[b][a]=c

dist = floyd_warshall(dist)

for i in range(N):
  for j in range(N):
    if dist[i][j]<=L:
      dist[i][j]=1
    else:
      dist[i][j]=INF

dist = floyd_warshall(dist)
dist[dist==INF]=0
#dist=dist.astype(int)
#print(dist)

Q=int(input())
ans=[0]*Q
for q in range(Q):
  s,t=map(int,input().split())
  s-=1
  t-=1
  ans[q]=int(dist[s][t]-1)

print(*ans,sep='\n')



import sys
readline = sys.stdin.readline

import math

# 最短距離をワーシャルフロイドで求める
# 最短距離がL以下の街には燃料1で行けるので、辺を貼り直してワーシャルフロイド

N,M,L = map(int,readline().split())

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import csgraph_from_dense
INF = 10 ** 9 + 1
G = [[INF for i in range(N)] for j in range(N)]
for i in range(M):
  a,b,c = map(int,readline().split())
  G[a - 1][b - 1] = c
  G[b - 1][a - 1] = c
G = csgraph_from_dense(G, null_value=INF)
d = floyd_warshall(G)

EG = [[INF for i in range(N)] for j in range(N)]
for i in range(N):
  for j in range(N):
    if d[i][j] <= L:
      EG[i][j] = 1

EG = csgraph_from_dense(EG, null_value=INF)
d = floyd_warshall(EG)

Q = int(readline())
for i in range(Q):
  s,t = map(int,readline().split())
  if d[s - 1][t - 1] != math.inf:
    print(int(d[s - 1][t - 1] - 1))
  else:
    print(-1)

from scipy.sparse.csgraph import floyd_warshall
import numpy as np

N, M, L = list(map(int, input().split()))
graph = np.array([[0 if i == j else float("inf")
                   for i in range(N)] for j in range(N)])
graph2 = np.array([[0 if i == j else float("inf")
                   for i in range(N)] for j in range(N)])


for _ in range(M):
    a, b, c = list(map(int, input().split()))
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c
dist = floyd_warshall(graph)

graph2[(dist <= L) & (dist != 0)] = 1
dist2 = floyd_warshall(graph2)
dist2[dist2 == float("inf")] = 0

Q = int(input())
for _ in range(Q):
    s, t = list(map(int, input().split()))
    print((int(dist2[s - 1, t - 1]) - 1))



# 2019-11-19 10:28:31(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import numpy as np 


def main():
    n, m, l = list(map(int, sys.stdin.readline().split()))
    ABCQST = np.array(sys.stdin.read().split(), np.int64)
    ABC = ABCQST[:m * 3]
    A, B, C = ABC[::3], ABC[1::3], ABC[2::3]
    ST = ABCQST[m * 3 + 1:]
    S, T = ST[::2], ST[1::2]

    dist = csr_matrix((C, (A, B)), (n+1, n+1))
    min_dist = floyd_warshall(dist, directed=False)

    filling_times = np.full((n+1, n+1), np.inf)
    np.diagonal(filling_times, 0)
    filling_times[min_dist <= l] = 1

    min_filling_times = floyd_warshall(filling_times, directed=False)

    min_filling_times[min_filling_times == np.inf] = 0
    # 最後に-1する
    min_filling_times = min_filling_times.astype(int)

    res = min_filling_times[S, T] - 1
    print(('\n'.join(res.astype(str))))


def __starting_point():
    main()

__starting_point()

from math import isinf
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix

INF = float('inf')

def main():
    N, M, L = list(map(int, input().split()))
    E = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        E[a - 1][b - 1] = c
        E[b - 1][a - 1] = c
    EE = shortest_path(csr_matrix(E))
    E = [[1 if EE[i][j] <= L else INF for j in range(N)] for i in range(N)]
    EE = shortest_path(csr_matrix(E))
    Q = int(input())
    for _ in range(Q):
        s, t = list(map(int, input().split()))
        x = EE[s - 1][t - 1]
        print((-1 if isinf(x) else int(x) - 1))
        

main()


from scipy.sparse.csgraph import floyd_warshall
from numpy import where
n,m,l=map(int,input().split())
abc=[list(map(int,input().split()))for i in range(m)]
q=int(input())
st=[list(map(int, input().split()))for i in range(q)]
t=[[float("inf")]*n for _ in range(n)]
for a,b,c in abc:
 if c<=l:t[a-1][b-1]=c
f=floyd_warshall(t,0)
l=floyd_warshall(where(f<=l,1,f),0)
for s, t in st:print(-1if l[s-1,t-1]==float("inf")else int(l[s-1,t-1])-1)

def resolve():
    from scipy.sparse.csgraph import floyd_warshall
    import numpy as np
    import sys
    input = sys.stdin.readline
    n, m, l = list(map(int, input().split()))
    inf = 10 ** 20
    ar = [[0] * n for _ in range(n)]
    for _ in range(m):
        a, b, c = list(map(int, input().split()))
        ar[a - 1][b - 1] = c
    x = floyd_warshall(ar, directed=False)
    br = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if x[i, j] <= l:
                br[i][j] = 1
    y = floyd_warshall(br, directed=False)
    q = int(input())
    for _ in range(q):
        s, t = list(map(int, input().split()))
        p = y[s - 1, t - 1]
        print((int(p) - 1 if p < inf else -1))


def __starting_point():
    resolve()

__starting_point()

import numpy as np

from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

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

if M == 0:
    Q = int(input())
    for _ in range(Q):
        print((-1))
    return

R = np.array([tuple(map(int, input().split())) for _ in range(M)])
matr = csr_matrix((R[:, 2], (R[:, 0] - 1, R[:, 1] - 1)), shape=(N, N))
way = floyd_warshall(matr, directed=False).astype(int)

way = np.where((way >= 0) & (way <= L), 1, 0)
matr_replenishment = csr_matrix(way)
way_replenishment = floyd_warshall(matr_replenishment, directed=False).astype(int).tolist()

Q = int(input())
for _ in range(Q):
    S, T = list(map(int, input().split()))
    print((res - 1 if (res := way_replenishment[S - 1][T - 1]) >= 0 else -1))


N, M, L = (int(i) for i in input().split())

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

graph = [[0]*N for i in range(N)]
for i in range(M):
    a, b, c = (int(i) for i in input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

graph = csr_matrix(graph)
d = floyd_warshall(csgraph=graph, directed=False)

new_graph = [[0]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if d[i][j] <= L:
            new_graph[i][j] = 1
            new_graph[j][i] = 1

graph = csr_matrix(new_graph)
d = floyd_warshall(csgraph=graph, directed=False)
Q = int(input())
for i in range(Q):
    s, t = (int(i) for i in input().split())
    if d[s-1][t-1] == float("inf"):
        print("-1")
    else:
        print(int(d[s-1][t-1]-1))

from scipy.sparse.csgraph import floyd_warshall

n, m, l = map(int, input().split())
inf = 10**12
d = [[inf for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
dd = floyd_warshall(d)
ddd = [[inf for i in range(n)] for i in range(n)]
for i in range(n):
  for j in range(n):
    if dd[i][j] <= l:
      ddd[i][j] = 1
dddd =floyd_warshall(ddd)
q = int(input())
for i in range(q):
  s, t = map(int, input().split())
  if dddd[s-1][t-1] == inf:
    print(-1)
  else:
    print(int(dddd[s-1][t-1]-1))

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n, m, l = map(int, input().split())
INF = 1 << 60

# 距離のmatrixを作る
dist = [[INF] * n for _ in range(n)]

# 対角行列の成分は０
for i in range(n):
    dist[i][i] = 0

# 燃料の最大値より小さい場合に辺が張れる
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if c > l:
        continue
    dist[a][b] = c
    dist[b][a] = c

# 全点間の最短距離を求める
dist = floyd_warshall(csr_matrix(dist))

# 初期状態を１にする。燃料が足りない経路は迂回したいのでINFを置いておく
dist2 = np.full_like(dist, 1)
dist2[np.where(dist > l)] = INF

# 足し込むことで何回給油するべきかがわかる
dist2 = floyd_warshall(dist2, directed=False)
dist2 = dist2.astype(int)

# 無限大の経路は辿れない。-1を出力したいので０を置いていく
dist2[dist2 == INF] = 0

q = int(input())

# 初期状態を１としているので、１を引いて答えとする
ans = []
for _ in range(q):
    s, t = map(int, input().split())
    ans.append(dist2[s - 1, t - 1] - 1)

print(*ans, sep="\n")

#import numpy as np
from scipy.sparse.csgraph import floyd_warshall, csgraph_from_dense
from scipy.sparse import csr_matrix

N,M,L = list(map(int, input().split()))
V = [[ 10**12 for _ in range(N) ] for _ in range(N)]
for _ in range(M):
  a,b,c = list(map(int, input().split()))
  a,b = a-1, b-1
  V[a][b] = c
  V[b][a] = c
  
G = csgraph_from_dense(V, null_value=10**12)
d = floyd_warshall(G)

V2 = [[ 10**9 for _ in range(N) ] for _ in range(N)]
for i in range(N):
  for j in range(N):
    if 0 < d[i][j] <= L:
      V2[i][j] = 1
      
G2 = csgraph_from_dense(V2, null_value=10**9)
d2 = floyd_warshall(G2)

Q = int(input())
for _ in range(Q):
  s,t = list(map(int, input().split()))
  s,t = s-1, t-1
  print((int(d2[s][t])-1 if d2[s][t] < 1000 else -1))


from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall


def solve():
    N, M, L = map(int, input().split())
    dist = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(M):
        a, b, c = map(int, input().split())
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c
    fw = floyd_warshall(csr_matrix(dist))

    ok = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if fw[i][j] <= L:
                ok[i][j] = 1
    ans = floyd_warshall(csr_matrix(ok))

    Q = int(input())
    for i in range(Q):
        s, t = map(lambda x: int(x)-1, input().split())
        if ans[s][t] < N:
            print(int(ans[s][t])-1)
        else:
            print(-1)


def __starting_point():
    solve()
__starting_point()

from enum import Enum
from queue import Queue

import numpy as np

import collections
import bisect
import sys
import math

from scipy.sparse.csgraph import floyd_warshall

BIG_NUM = 200000000000
MOD = 1000000007
EPS = 0.000000001

def warshall_floyd(d,n):
    #d[i][j]:iからjへの最短距離
    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

N,M,L = list(map(int,input().split()))
d = [[float("inf") for i in range(N)] for j in range(N)]
for i in range(M):
    a,b,c = list(map(int,input().split()))
    d[a-1][b-1] = c
    d[b-1][a-1] = c
for i in range(N):
    d[i][i] = 0
d = floyd_warshall(d)
for i in range(N):
    for j in range(i,N):
        if d[i][j] <= L:
            d[i][j] = 1
            d[j][i] = 1
        else:
            d[i][j] = float("inf")
            d[j][i] = float("inf")
    d[i][i] = 1
d = floyd_warshall(d)
Q = int(input())
for q in range(Q):
    s,t = list(map(int,input().split()))
    if d[s-1][t-1] == float("inf"):
        print((-1))
    else:
        print((int(d[s-1][t-1])-1))


import sys
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
input = sys.stdin.readline

N, M, L = list(map(int, input().split()))
graph = np.array([[0 if i == j else float("inf")
                   for i in range(N)] for j in range(N)])
for _ in range(M):
    a, b, c = list(map(int, input().split()))
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c

Q = int(input())
dist = floyd_warshall(graph)


graph2 = np.array([[float("inf")] * N for _ in range(N)])
np.fill_diagonal(graph2, 0)
graph2[(dist <= L) & (dist != 0)] = 1

dist2 = floyd_warshall(graph2)
dist2[dist2 == float("inf")] = 0

for _ in range(Q):
    s, t = list(map(int, input().split()))
    print((int(dist2[s - 1, t - 1]) - 1))


import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

G = np.full((N, N), np.inf)
np.fill_diagonal(G, 0)
for _ in range(M):
    a, b, c = list(map(int, input().split()))
    G[a-1][b-1] = G[b-1][a-1] = c
D = floyd_warshall(G, directed=False)

G2 = np.full((N, N), np.inf)
np.fill_diagonal(G2, 0)
G2[D <= L] = 1
D2 = floyd_warshall(G2, directed=False)

Q = int(input())
for _ in range(Q):
    a, b = [int(x) - 1 for x in input().split()]
    if D2[a][b] == np.inf:
        print((-1))
    else:
        print((int(D2[a][b]) - 1))


import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
inf = float("inf")
N, M, L = map(int, input().split())
graph = np.zeros((N, N))
for _ in range(M):
    A, B, C = map(int, input().split())
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C
shortest_paths = dijkstra(csr_matrix(graph), directed=False)
graph = np.full((N, N), inf)
for i in range(N):
    for j in range(N):
        if shortest_paths[i][j] <= L:
            graph[i][j] = 1

Q = int(input())
def int_(num_str):
    return int(num_str) - 1

costs = dijkstra(csr_matrix(graph), directed=False)
for _ in range(Q):
    s, t = map(int_, input().split())
    print(int(costs[s][t])-1 if costs[s][t] != inf else -1)

import sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import floyd_warshall

def main():
    N,M,L = list(map(int,input().split()))
    edge = np.zeros((N,N))
    for _ in range(M):
        a,b,c = list(map(int,input().split()))
        edge[a-1][b-1] = edge[b-1][a-1] = c
        
    length = floyd_warshall(edge,directed=False)
    ref = np.where(length<=L,1,0)
    ans = floyd_warshall(ref,directed=False)
    Q = int(input())
    for _ in range(Q):
        s,t = list(map(int,input().split()))
        if ans[s-1][t-1] == float("inf"):
            print((-1))
        else:
            print((int(ans[s-1][t-1])-1))

def __starting_point():
    main()

__starting_point()

from scipy.sparse.csgraph import floyd_warshall

# ダイクストラを二回行う
N, M, L = list(map(int, input().split()))
graph = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c

graph = floyd_warshall(graph)
another = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if graph[i][j] <= L:
            another[i][j] = 1
another = floyd_warshall(another)
Q = int(input())
for _ in range(Q):
    s, t = [int(x)-1 for x in input().split()]
    if another[s][t] == float('inf'):
        print((-1))
    else:
        print((int(another[s][t])-1))


import sys
input = sys.stdin.readline

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

def main():
  n, m, l = map(int, input().split())
  F = np.zeros((n, n))
  for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    F[a, b] = c
    F[b, a] = c
  csr = csr_matrix(F)
  A = floyd_warshall(csr)
  G = np.zeros((n, n))
  for i in range(n-1):
    for j in range(i+1, n):
      if A[i][j] <= l:
        G[i, j] = 1
        G[j, i] = 1
  ncsr = csr_matrix(G)
  B =  floyd_warshall(ncsr)
  q = int(input())
  for _ in range(q):
    s, t = map(int, input().split())
    k = B[s-1][t-1]
    if k == float("inf"):
      print(-1)
    else:
      print(int(k)-1)
      
def __starting_point():
  main()
__starting_point()


import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
def resolve():
    INF = 10 ** 18
    N, M, L = list(map(int, input().split()))
    G = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1
        G[a][b] = G[b][a] = c

    G = csr_matrix(G)
    dist = floyd_warshall(G, directed=False)

    G2 = np.full((N, N), np.inf)  # 値をINFにした配列
    np.fill_diagonal(G2, 0)  # G[i][i]は動いていない状態なのでコスト0
    G2[dist <= L] = 1

    dist2 = floyd_warshall(G2, directed=False)

    Q = int(input())
    for _ in range(Q):
        a, b = [int(x) - 1 for x in input().split()]
        if dist2[a][b] == np.inf:
            print((-1))
        else:
            print((int(dist2[a][b]) - 1))


def __starting_point():
    resolve()

__starting_point()

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
inf = float("inf")
N, M, L = list(map(int, input().split()))
graph = np.zeros((N, N))
for _ in range(M):
    A, B, C = list(map(int, input().split()))
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C
shortest_paths = dijkstra(csr_matrix(graph), directed=False)
graph = np.full((N, N), inf)
for i in range(N):
    for j in range(N):
        if shortest_paths[i][j] <= L:
            graph[i][j] = 1

Q = int(input())
def int_(num_str):
    return int(num_str) - 1

costs = dijkstra(csr_matrix(graph), directed=False)
for _ in range(Q):
    s, t = list(map(int_, input().split()))
    print((int(costs[s][t])-1 if costs[s][t] != inf else -1))


def main():
    from sys import stdin
    input=stdin.readline
    
    import numpy as np
    import scipy.sparse.csgraph as sp

    n, m, l = list(map(int, input().split()))
    abc = [list(map(int, input().split())) for _ in [0]*m]
    q = int(input())
    st = [list(map(int, input().split())) for _ in [0]*q]
    inf = 10**12
    dist = np.full((n, n), inf, dtype=np.int64)
    for i in range(n):
        dist[i][i] = 0
    for a, b, c in abc:
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c
    dist = sp.shortest_path(dist)

    inf = 10**3
    dist2 = np.full((n, n), inf, dtype=np.int16)
    for i in range(n):
        for j in range(n):
            if dist[i][j] <= l:
                dist2[i][j] = 1
    dist2 = sp.shortest_path(dist2)

    for i in range(n):
        for j in range(n):
            if dist2[i][j] == inf:
                dist2[i][j] = -1
            else:
                dist2[i][j] -= 1
    for s, t in st:
        print((int(dist2[s-1][t-1])))


main()


import sys
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
input = sys.stdin.readline

N, M, L = list(map(int, input().split()))
graph = np.array([[0 if i == j else float("inf")
                   for i in range(N)] for j in range(N)])
for _ in range(M):
    a, b, c = list(map(int, input().split()))
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c

Q = int(input())
dist = floyd_warshall(graph)


graph2 = np.array([[float("inf")] * N for _ in range(N)])
np.fill_diagonal(graph2, 0)
graph2[(dist <= L) & (dist != 0)] = 1

dist2 = floyd_warshall(graph2)
dist2[dist2 == float("inf")] = 0

for _ in range(Q):
    s, t = list(map(int, input().split()))
    print((int(dist2[s - 1, t - 1]) - 1))


import sys
input = sys.stdin.readline

N, M, L = (int(i) for i in input().split())

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

graph = [[0]*N for i in range(N)]
for i in range(M):
    a, b, c = (int(i) for i in input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

graph = csr_matrix(graph)
d = floyd_warshall(csgraph=graph, directed=False)

new_graph = [[0]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if d[i][j] <= L:
            new_graph[i][j] = 1
            new_graph[j][i] = 1

graph = csr_matrix(new_graph)
d = floyd_warshall(csgraph=graph, directed=False)
Q = int(input())
for i in range(Q):
    s, t = (int(i) for i in input().split())
    if d[s-1][t-1] == float("inf"):
        print("-1")
    else:
        print(int(d[s-1][t-1]-1))

from scipy.sparse import*
f=csgraph.johnson
n,m,l,*t=map(int,open(0).read().split())
m*=3
[*map(print,f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1)]

import sys
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix

input = sys.stdin.readline

n, m, l = list(map(int, input().split()))
g_dense = np.zeros((n, n))

for _ in range(m):
    a, b, c = map(int, input().split())
    g_dense[a-1][b-1] = c

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

path = shortest_path(g_dense, directed=False)

g_dense = np.zeros((n, n))

for i in range(n):
    for j in range(n):
        if path[i][j] <= l:
            g_dense[i][j] = 1

path = shortest_path(g_dense, directed=False)

INF = float('inf')

for s,t in st:
    ans = path[s-1][t-1]
    if ans == INF:
        print(-1)
    else:
        print(int(ans) - 1)

from scipy.sparse.csgraph import floyd_warshall
N,M,L,*X = map(int, open(0).read().split())
ls = X[:3*M]
Els = [[0]*N for i in range(N)]
Q = X[3*M]
query = X[3*M+1:]
for a,b,c in zip(*[iter(ls)]*3):
  if c<=L:
    Els[a-1][b-1] = c
    Els[b-1][a-1] = c
dist = floyd_warshall(Els)
      
Els2 = [[0]*N for i in range(N)]
for i in range(N):
  for j in range(N):
    if dist[i][j]<=L:
      Els2[i][j] = 1
ans = floyd_warshall(Els2)

for s,t in zip(*[iter(query)]*2):
  if ans[s-1][t-1]==float('inf'):
    print(-1)
    continue
  print(int(ans[s-1][t-1])-1)

def resolve():
    from scipy.sparse.csgraph import floyd_warshall
    import numpy as np
    import sys
    input = sys.stdin.readline
    n, m, l = list(map(int, input().split()))
    inf = 10 ** 20
    ar = np.zeros((n, n))
    for _ in range(m):
        a, b, c = list(map(int, input().split()))
        ar[a - 1, b - 1] = c
        ar[b - 1, a - 1] = c
    x = floyd_warshall(ar)
    br = np.zeros((n, n))
    for i in range(n):
        for j in range(i + 1, n):
            if x[i, j] <= l:
                br[i, j] = 1
                br[j, i] = 1
    y = floyd_warshall(br)
    q = int(input())
    for _ in range(q):
        s, t = list(map(int, input().split()))
        p = y[s - 1, t - 1]
        print((int(p) - 1 if p < inf else -1))


def __starting_point():
    resolve()

__starting_point()

n,m,l=list(map(int,input().split()))

#基本的にワーシャルフロイドの場合、行列式のリストで距離を保管する
from scipy.sparse import csr_matrix
from scipy.sparse import csgraph 
d = [[10**12 for i in range(n+1)] for i in range(n+1)]
for i in range(m):
    x,y,z = list(map(int,input().split()))
    #有向グラフか無向グラフかによってここで場合わけが生じる
    d[x][y] = z
    d[y][x] = z
    
for i in range(n+1):
    d[i][i] = 0 #自身のところに行くコストは０
q=int(input())
que=[]
for _ in range(q):
    s,t=list(map(int,input().split()))
    que.append((s,t))
       
csr=csr_matrix(d)
K=csgraph.shortest_path(csr,method="FW",directed=True)
e = [[10**12 for i in range(n+1)] for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,n+1):
        if K[i][j]<=l:
            e[i][j]=1
            
for i in range(n+1):
    e[i][i]=0
    

A=csr_matrix(e)
ANS=csgraph.shortest_path(A,method="FW",directed=True)

for some in que:
    s,t=some[0],some[1]
    if int(ANS[s][t])<10**12:
        print((int(ANS[s][t])-1))
    else:
        print((-1))




n,m,l = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
q = int(input())
S = [list(map(int,input().split())) for i in range(q)]

from scipy.sparse.csgraph import floyd_warshall

for i in range(m):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        A[i][j] -= 1

for i in range(q):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        S[i][j] -= 1

M = [[float("inf")] * n for i in range(n)]

for i in range(n):
    M[i][i] = 0

for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             M[i][j] = min(M[i][j], M[i][k] + M[k][j])

M = floyd_warshall(M)

for i in range(n):
    for j in range(n):
        M[i][j] = 1 if M[i][j] <= l else float("inf")

for i in range(n):
    M[i][i] = 0

# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             M[i][j] = min(M[i][j], M[i][k] + M[k][j])

M = floyd_warshall(M)

for i in range(q):
    ans = M[S[i][0]][S[i][1]]-1
    if ans == float("inf"):
        ans = -1
    print(int(ans))

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

f=lambda:map(int,input().split())
N,M,L=f()
G=[[0]*N for _ in [0]*N]
for _ in [0]*M:
    a,b,c=f()
    G[a-1][b-1]=c
    G[b-1][a-1]=c
    
csr=csr_matrix(G)

D=floyd_warshall(csr)
INF=float('inf')
G=[[INF]*N for _ in [0]*N]
for i in range(N):
    for j in range(N):
        if i!=j and D[i][j]<=L:
            G[i][j]=1
            G[j][i]=1
csr=csr_matrix(G)
res=floyd_warshall(csr)
Q=int(input())
for _ in [0]*Q:
    s,t=f()
    r=res[s-1][t-1]
    print(int(r-1) if r<INF else -1)

#dame datta...
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
def main():
    N, M, L = list(map(int, input().split()))
    l = [[0] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        if c > L:
            continue
        l[a-1][b-1] = c
        l[b-1][a-1] = c
    G = csr_matrix(l)
    d = floyd_warshall(G)
    l = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if d[i][j] <= L:
                l[i][j] = 1
    G = csr_matrix(l)
    d = floyd_warshall(G)
    Q = int(input())
    for _ in range(Q):
        s, t = list(map(int, input().split()))
        s -= 1
        t -= 1
        x = d[s][t]
        if x != float('inf'):
            print((int(x)-1))
        else:
            print((-1))
main()


from scipy.sparse.csgraph import floyd_warshall

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

edges = [[0] * N for _ in range(N)]

for _ in range(M):
    A,B,C = list(map(int, input().split()))
    edges[A-1][B-1] = C
    edges[B-1][A-1] = C

Q = int(input())
queries = []

for _ in range(Q):
    queries.append(list(map(int,input().split())))

# use flord warshall to find min path between all towns
edges = floyd_warshall(edges)

# if the two towns can be travelled to on one tank, add to our fuel graph with distance 1
for i in range(N):
    for j in range(N):
        if edges[i][j] <= L:
            edges[i][j] = 1
        else:
            edges[i][j] = 0

# use flord warshall to find min number of fuel tanks to travel between two towns
edges = floyd_warshall(edges)

for query in queries:
    s = query[0] - 1
    t = query[1] - 1
    num_tanks = edges[s][t] - 1
    if num_tanks != float('inf'):
        print((int(num_tanks)))
    else:
        print("-1")


n,m,l = map(int, input().split())
wf=[[float("inf") for i in range(n)] for j in range(n)]
for i in range(m):
    a,b,c = list(map(int,input().split()))
    wf[a-1][b-1] = c
    wf[b-1][a-1] = c
q = int(input())
st=[list(map(int,input().split())) for i in range(q)]

from scipy.sparse.csgraph import floyd_warshall
for i in range(n):
    wf[i][i]=0
wf=floyd_warshall(wf)

for i in range(n):
    for j in range(n):
        if wf[i][j] <= l:
            wf[i][j] = 1
        else:
            wf[i][j] = float("inf")

wf=floyd_warshall(wf)

for que in st:
    s,t=que
    if wf[s-1][t-1] == float("inf"):
        print(-1)
    else:
        print(int(wf[s-1][t-1]-1))

from scipy.sparse.csgraph import floyd_warshall
import numpy as np

N, M, L = list(map(int, input().split()))
inf = 10**9 + 1
dist = [[inf] * N for i in range(N)]
for i in range(M):
    A, B, C = list(map(int, input().split()))
    dist[A-1][B-1] = dist[B-1][A-1] = C

dist = floyd_warshall(dist, directed=False)
dist = np.where(dist <= L, 1, inf)
dist = floyd_warshall(dist, directed=False)
dist = np.where(dist < inf, dist-1, -1)

Q = int(input())
for i in range(Q):
    s, t = list(map(int, input().split()))
    print((int(dist[s-1, t-1])))