AtCoder Beginner Contest 143 - Travel by Car

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.

Source: atcoder | Difficulty: MEDIUM_HARD


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


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

def bell(g, n):
	for k in range(n):
		for i in range(n - 1):
			for j in range(i + 1, n):
				if g[i][j] > g[i][k] + g[k][j]:
					g[i][j] = g[i][k] + g[k][j]
					g[j][i] = g[i][j]
	return g
g = bell(g, n)
for i in range(n):
	for j in range(n):
		if i == j:
			g[i][j] = 0
		elif g[i][j] <= l:
			g[i][j] = 1
		else:
			g[i][j] = 1 << 30
g = bell(g, n)
q = int(input())
for _ in range(q):
	(s, t) = map(int, input().split())
	if g[s - 1][t - 1] >> 30:
		print(-1)
	else:
		print(g[s - 1][t - 1] - 1)


from scipy.sparse.csgraph import floyd_warshall
(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))


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


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 = [[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)
	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 sys
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
	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()


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


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


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

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	M = int(next(tokens))
	L = int(next(tokens))
	A = [int()] * M
	B = [int()] * M
	C = [int()] * M
	for i in range(M):
		A[i] = int(next(tokens))
		B[i] = int(next(tokens))
		C[i] = int(next(tokens))
	Q = int(next(tokens))
	s = [int()] * Q
	t = [int()] * Q
	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():
	main()
__starting_point()


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


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


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)


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


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


(N, M, L) = map(int, input().split())
INF = 10 ** 12
dp = [[INF] * N for i in range(N)]
fp = [[INF] * N for i in range(N)]
for i in range(N):
	dp[i][i] = 0
	fp[i][i] = 0
k = [[0] * N for i in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	dp[a - 1][b - 1] = c
	dp[b - 1][a - 1] = c
for i in range(N):
	for j in range(N):
		for h in range(N):
			dp[j][h] = min(dp[j][h], dp[j][i] + dp[i][h])
for j in range(N):
	for h in range(N):
		if dp[j][h] <= L:
			fp[j][h] = 1
for i in range(N):
	for j in range(N):
		for h in range(N):
			fp[j][h] = min(fp[j][h], fp[j][i] + fp[i][h])
Q = int(input())
for i in range(Q):
	(s, t) = map(int, input().split())
	s = s - 1
	t = t - 1
	if fp[s][t] == INF:
		print(-1)
	else:
		print(fp[s][t] - 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())
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 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 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.astype(int)
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')


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

def warshall_floyd(d, v):
	for k in range(v):
		for i in range(v):
			for j in range(v):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
inf = 10 ** 15
d = [[inf] * n for _ in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = min(d[a - 1][b - 1], c)
	d[b - 1][a - 1] = min(d[b - 1][a - 1], c)
warshall_floyd(d, n)
e = [[inf] * n for _ in range(n)]
for i in range(n):
	for j in range(i + 1, n):
		if d[i][j] <= l:
			e[i][j] = min(e[i][j], 1)
			e[j][i] = min(e[j][i], 1)
warshall_floyd(e, n)
q = int(input())
for _ in range(q):
	(s, t) = map(int, input().split())
	print(e[s - 1][t - 1] - 1 if e[s - 1][t - 1] < inf else -1)


def warshall_floid(d):
	for k in range(1, n + 1):
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
	return d
(n, m, l) = map(int, input().split())
d = [[10 ** 12] * (n + 1) for _ in range(n + 1)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	d[a][b] = c
	d[b][a] = c
d = warshall_floid(d)
for i in range(1, n + 1):
	for j in range(1, n + 1):
		if d[i][j] <= l:
			d[i][j] = 1
		else:
			d[i][j] = 10 ** 12
d = warshall_floid(d)
q = int(input())
for i in range(q):
	(s, t) = map(int, input().split())
	if d[s][t] >= 10 ** 12:
		print(-1)
	else:
		print(d[s][t] - 1)


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


(n, m, l) = map(int, input().split())
inf = 10000000000
g = [[inf for i in range(n)] for j in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	g[a - 1][b - 1] = c
	g[b - 1][a - 1] = c
for k in range(n):
	for i in range(n):
		for j in range(n):
			g[i][j] = min(g[i][j], g[i][k] + g[k][j])
r = [[inf for i in range(n)] for j in range(n)]
for i in range(n):
	for j in range(n):
		if g[i][j] <= l:
			r[i][j] = 1
		elif g[i][j] >= inf:
			r[i][j] = inf
for k in range(n):
	for i in range(n):
		for j in range(n):
			r[i][j] = min(r[i][j], r[i][k] + r[k][j])
q = int(input())
for i in range(q):
	(s, e) = map(int, input().split())
	if r[s - 1][e - 1] >= inf:
		print(-1)
	else:
		print(r[s - 1][e - 1] - 1)


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
readline = sys.stdin.readline
import math
(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)


(n, m, l) = map(int, input().split())
g = [[float('inf')] * n for _ in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	g[a][b] = c
	g[b][a] = c
for k in range(n):
	for i in range(n):
		for j in range(n):
			g[i][j] = min(g[i][j], g[i][k] + g[k][j])
h = [[float('inf')] * n for _ in range(n)]
for i in range(n):
	for j in range(n):
		if g[i][j] <= l:
			h[i][j] = 1
for k in range(n):
	for i in range(n):
		for j in range(n):
			h[i][j] = min(h[i][j], h[i][k] + h[k][j])
Q = int(input())
for _ in range(Q):
	(s, t) = map(int, input().split())
	s -= 1
	t -= 1
	if h[s][t] == float('inf'):
		print(-1)
	else:
		print(h[s][t] - 1)


(n, m, l) = map(int, input().split())
d = [[10 ** 18] * n for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	if c <= l:
		d[a - 1][b - 1] = c
		d[b - 1][a - 1] = c
for i in range(n):
	d[i][i] = 0
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])
for i in range(n):
	for j in range(n):
		if d[i][j] <= l:
			d[i][j] = 1
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])
q = int(input())
for i in range(q):
	(s, t) = map(int, input().split())
	s -= 1
	t -= 1
	print(d[s][t] - 1 if d[s][t] - 1 < 999999999999999999 else -1)


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 = [[10 ** 10 for _ in range(n)] for _ in range(n)]
for i in range(n):
	d[i][i] = 0
for i in range(m):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = c
p = [[10 ** 5 for _ in range(n)] for _ in range(n)]
d = warshall_floyd(d)
for i in range(n):
	for j in range(n):
		if d[i][j] <= l:
			p[i][j] = 1
p = warshall_floyd(p)
q = int(input())
for i in range(q):
	(s, t) = map(int, input().split())
	if p[s - 1][t - 1] == 10 ** 5:
		print(-1)
		continue
	print(p[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]))


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):
	for j in range(2):
		A[i][j] -= 1
for i in range(q):
	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]
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
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
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 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()


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)


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)


import sys
input = sys.stdin.readline
(N, M, L) = 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 = (L + 1) * N
d = [[INF] * N for _ in [0] * N]
for i in range(N):
	d[i][i] = 0
for (a, b, c) in ABC:
	a -= 1
	b -= 1
	d[a][b] = c
	d[b][a] = c

def Warshall_Floyd(d, N=None):
	if N == None:
		N = len(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])
Warshall_Floyd(d, N)
d2 = [None] * N
for (i, row) in enumerate(d):
	d2[i] = [1 if e <= L else INF for e in row]
	d2[i][i] = 0
Warshall_Floyd(d2, N)
for (s, t) in ST:
	s -= 1
	t -= 1
	ans = d2[s][t] % INF - 1
	print(ans)


def warshall_floyd(edge):
	e = edge
	for k in range(len(e)):
		for i in range(len(e)):
			for j in range(len(e)):
				e[i][j] = min(e[i][j], e[i][k] + e[k][j])
	return e
(n, m, l) = map(int, input().split())
edge = [n * [10 ** 18] for _ in range(n)]
for i in range(n):
	edge[i][i] = 0
for i in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	edge[a][b] = edge[b][a] = c
edge = warshall_floyd(edge)
edge2 = [n * [10 ** 18] for _ in range(n)]
for i in range(n):
	edge2[i][i] = 0
	for j in range(n):
		if edge[i][j] <= l:
			edge2[i][j] = 1
edge2 = warshall_floyd(edge2)
q = int(input())
for i in range(q):
	(s, t) = map(int, input().split())
	s -= 1
	t -= 1
	ans = edge2[s][t]
	if ans == 10 ** 18:
		print(-1)
	else:
		print(ans - 1)


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 = 1e-09

def warshall_floyd(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
(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
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)


(N, M, L) = map(int, input().split())
G = [[10 ** 15 for i in range(N)] for i in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	G[a - 1][b - 1] = c
	G[b - 1][a - 1] = c
for k in range(N):
	for i in range(N):
		for j in range(N):
			G[i][j] = min(G[i][j], G[i][k] + G[k][j])
H = [[10 ** 15 for i in range(N)] for i in range(N)]
for i in range(N):
	for j in range(N):
		if G[i][j] <= L:
			H[i][j] = 1
for k in range(N):
	for i in range(N):
		for j in range(N):
			H[i][j] = min(H[i][j], H[i][k] + H[k][j])
Q = int(input())
for line in range(Q):
	(s, t) = map(int, input().split())
	s -= 1
	t -= 1
	if H[s][t] == 10 ** 15:
		print(-1)
	else:
		print(H[s][t] - 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)
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)
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
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)
	np.fill_diagonal(G2, 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()


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
from scipy.sparse import csr_matrix
(n, m, l) = list(map(int, input().split()))

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


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


import sys
input = sys.stdin.readline
(N, M, L) = map(int, input().split())

def war(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
INF = (L + 1) * N
d = [[INF] * N for _ in range(N)]
d2 = [[INF] * N for _ in range(N)]
for _ in range(M):
	(A, B, C) = map(int, input().split())
	if C > L:
		continue
	d[A - 1][B - 1] = C
	d[B - 1][A - 1] = C
for i in range(N):
	d[i][i] = 0
d = war(d)
for i in range(N):
	for j in range(N):
		if d[i][j] <= L:
			d2[i][j] = 1
for i in range(N):
	d2[i][i] = 0
d2 = war(d2)
Q = int(input())
for i in range(Q):
	(s, t) = map(int, input().split())
	print(d2[s - 1][t - 1] % INF - 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 = 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()


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


import sys
input = sys.stdin.readline
inf = 10 ** 9 + 7
(n, m, l) = map(int, input().split())
D = [[inf] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	D[a][b] = c
	D[b][a] = c
for k in range(1, n + 1):
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			D[i][j] = min(D[i][j], D[i][k] + D[k][j])
DD = [[inf] * (n + 1) for _ in range(n + 1)]
for x in range(1, n + 1):
	for y in range(1, n + 1):
		if D[x][y] <= l:
			DD[x][y] = 1
for k in range(1, n + 1):
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			DD[i][j] = min(DD[i][j], DD[i][k] + DD[k][j])
q = int(input())
for _ in range(q):
	(s, t) = map(int, input().split())
	if DD[s][t] == inf:
		print(-1)
	else:
		print(DD[s][t] - 1)


import sys
I = sys.stdin.readlines()
(N, M, L) = map(int, I[0].split())
(a, b, c) = (0, 0, 0)
D = [[L + 1] * N for i in range(N)]
for i in range(M):
	(a, b, c) = map(int, I[i + 1].split())
	(a, b) = (a - 1, b - 1)
	D[a][b] = c
	D[b][a] = c
for i in range(N):
	D[i][i] = 0
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])
D2 = [[N * N + 2] * N for i in range(N)]
for i in range(N):
	D2[i][i] = 0
	for j in range(N):
		if D[i][j] <= L:
			D2[i][j] = 1
for k in range(N):
	for i in range(N):
		for j in range(N):
			D2[i][j] = min(D2[i][j], D2[i][k] + D2[k][j])
Q = int(I[M + 1])
for i in range(Q):
	(a, b) = map(int, I[i + 2 + M].split())
	if N < D2[a - 1][b - 1]:
		print(-1)
	else:
		print(D2[a - 1][b - 1] - 1)


(N, M, L) = map(int, input().split())
D = [[1000000000000] * N for i in range(N)]
for i in range(N):
	D[i][i] = 0
for i in range(M):
	(A, B, C) = map(int, input().split())
	(A, B) = (A - 1, B - 1)
	D[A][B] = C
	D[B][A] = C
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])
E = [[1000000000000] * N for i in range(N)]
for i in range(N):
	E[i][i] = 0
for i in range(N):
	for j in range(N):
		if D[i][j] <= L:
			E[i][j] = 1
for k in range(N):
	for i in range(N):
		for j in range(N):
			E[i][j] = min(E[i][j], E[i][k] + E[k][j])
Q = int(input())
for i in range(Q):
	(s, t) = map(int, input().split())
	(s, t) = (s - 1, t - 1)
	if E[s][t] == 1000000000000:
		r = -1
	else:
		r = E[s][t] - 1
	print(r)


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


def warshall_floyd(G):
	import copy
	ret = copy.deepcopy(G)
	for k in range(N):
		for i in range(N):
			for j in range(N):
				ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j])
	return ret
INF = 10 ** 10
(N, M, L) = map(int, input().split())
G = [[INF] * N for _ in range(N)]
for i in range(M):
	(A, B, C) = map(int, input().split())
	(G[A - 1][B - 1], G[B - 1][A - 1]) = (C, C)
MinG = warshall_floyd(G)
GL = [[1 if MinG[i][j] <= L else INF for j in range(N)] for i in range(N)]
MinGL = warshall_floyd(GL)
Q = int(input())
for _ in range(Q):
	(s, t) = map(int, input().split())
	print(-1 if MinGL[s - 1][t - 1] == INF else MinGL[s - 1][t - 1] - 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)


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)


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)


def WarshallFloyd(M):
	N = len(M)
	for k in range(N):
		for j in range(N):
			for i in range(N):
				M[i][j] = min(M[i][j], M[i][k] + M[k][j])
	return M
INF = float('inf')
(N, M, L, *I) = map(int, open(0).read().split())
(ABC, ST) = (I[:3 * M], I[3 * M + 1:])
E = [[INF] * N for _ in range(N)]
for (a, b, c) in zip(*[iter(ABC)] * 3):
	E[a - 1][b - 1] = E[b - 1][a - 1] = c
E = WarshallFloyd(E)
for i in range(N):
	for j in range(N):
		if E[i][j] <= L:
			E[i][j] = 1
		else:
			E[i][j] = INF
E = WarshallFloyd(E)
for (s, t) in zip(*[iter(ST)] * 2):
	a = E[s - 1][t - 1] - 1
	print(-1 if a == INF else a)


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)


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


import sys
imput = sys.stdin.readline

def func(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())
road = [[10 ** 10] * N for i in range(N)]
for i in range(N):
	road[i][i] = 0
for i in range(M):
	(a, b, c) = map(int, input().split())
	road[a - 1][b - 1] = c
	road[b - 1][a - 1] = c
road = func(road)
ans = [[10 ** 5] * N for i in range(N)]
for i in range(N):
	for j in range(N):
		if road[i][j] <= L:
			ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
	(a, b) = map(int, input().split())
	o = ans[a - 1][b - 1]
	if o == 10 ** 5:
		print(-1)
	else:
		print(o - 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()


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


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


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


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


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)


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


3
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')
(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)
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)
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))


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)


def w(d):
	n = len(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())
inf = float('inf')
fuel = [[inf] * N for _ in range(N)]
for i in range(N):
	fuel[i][i] = 0
for _ in range(M):
	(a, b, c) = map(int, input().split())
	fuel[a - 1][b - 1] = fuel[b - 1][a - 1] = c
Q = int(input())
ST = [list(map(int, input().split())) for _ in range(Q)]
fuel = w(fuel)
for i in range(N):
	for j in range(N):
		if 0 < fuel[i][j] <= L:
			fuel[i][j] = 1
		elif fuel[i][j] != 0:
			fuel[i][j] = inf
fuel = w(fuel)
for st in ST:
	print(fuel[st[0] - 1][st[1] - 1] - 1 if fuel[st[0] - 1][st[1] - 1] != inf else -1)


(n, m, l) = map(int, input().split())
abe = [list(map(int, input().split())) for i in range(m)]
dist = [[10 ** 18 for i in range(n)] for i in range(n)]
for (a, b, e) in abe:
	dist[a - 1][b - 1] = e
	dist[b - 1][a - 1] = e
for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
for i in range(n):
	for j in range(n):
		if dist[i][j] <= l:
			dist[i][j] = 1
		else:
			dist[i][j] = 10 ** 18
for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
q = int(input())
for i in range(q):
	(s, t) = map(int, input().split())
	x = dist[s - 1][t - 1] - 1
	if x == 10 ** 18 - 1:
		print(-1)
	else:
		print(x)


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


(n, m, l) = map(int, input().split())
INF = 1 << 30
g = [[INF] * n for _ in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	g[a][b] = c
	g[b][a] = c
for k in range(n):
	for i in range(n):
		for j in range(n):
			g[i][j] = min(g[i][j], g[i][k] + g[k][j])
h = [[INF] * n for _ in range(n)]
for i in range(n):
	for j in range(n):
		if g[i][j] <= l:
			h[i][j] = 1
for k in range(n):
	for i in range(n):
		for j in range(n):
			h[i][j] = min(h[i][j], h[i][k] + h[k][j])
q = int(input())
for _ in range(q):
	(s, t) = map(lambda x: int(x) - 1, input().split())
	if h[s][t] == INF:
		print(-1)
	else:
		print(h[s][t] - 1)


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


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)]
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
nei_graph = floyd_warshall(nei_graph)
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))


(n, m, l) = map(int, input().split())
inf = 100000000000
wf = [[inf] * n for i in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	wf[a - 1][b - 1] = c
	wf[b - 1][a - 1] = c
for i in range(n):
	wf[i][i] = 0
for k in range(n):
	for i in range(n):
		for j in range(n):
			wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
for i in range(n):
	for j in range(n):
		if i != j:
			wf[i][j] = 1 if wf[i][j] <= l else inf
for k in range(n):
	for i in range(n):
		for j in range(n):
			wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
q = int(input())
for i in range(q):
	(s, t) = map(int, input().split())
	x = wf[s - 1][t - 1]
	print(-1 if x == inf else wf[s - 1][t - 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))


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
input = sys.stdin.readline
(N, M, L) = map(int, input().split())
d = [[10 ** 16 * (i != j) for j in range(N + 1)] for i in range(N + 1)]
for _ in range(M):
	(x, y, c) = map(int, input().split())
	d[x][y] = c
	d[y][x] = c
for k in range(N + 1):
	for i in range(N + 1):
		for j in range(N + 1):
			d[i][j] = min(d[i][j], d[i][k] + d[k][j])
dd = [[(d[i][j] <= L) + (d[i][j] > L) * 10 ** 16 for j in range(N + 1)] for i in range(N + 1)]
for k in range(N + 1):
	for i in range(N + 1):
		for j in range(N + 1):
			dd[i][j] = min(dd[i][j], dd[i][k] + dd[k][j])
for _ in range(int(input())):
	(s, t) = map(int, input().split())
	if dd[s][t] != 10 ** 16:
		print(dd[s][t] - 1)
	else:
		print(-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 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)


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(-1 if l[s - 1, t - 1] == float('inf') else int(l[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())
queries = []
for _ in range(Q):
	queries.append(list(map(int, 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 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')


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)


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