Buggy python submission (verdict: Runtime Error):
from itertools import product, combinations

INF = float('inf')
def floyd_warshall(E):
    N = len(E)
    dist = [[INF for _ in range(N)] for _ in range(N)]
    for v in V:
        dist[v][v] = 0
        for u, c in E[v]: dist[v][u] = c
    for k in V:        
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

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

E_charge = [[] for _ in V]
for u, v in combinations(V, 2):
    if dist[u][v] <= L:
        E_charge[u].append((v, 1))
        E_charge[v].append((u, 1))
charge = floyd_warshall(E_charge)

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

Fixed submission:
from itertools import product, combinations

INF = float('inf')
def floyd_warshall(E):
    N = len(E)
    dist = [[INF for _ in range(N)] for _ in range(N)]
    for v in range(N):
        dist[v][v] = 0
        for u, c in E[v]: dist[v][u] = c
    for k in range(N):        
        for i, j in product(range(N), repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

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

E_charge = [[] for _ in range(N)]
for u, v in combinations(range(N), 2):
    if dist[u][v] <= L:
        E_charge[u].append((v, 1))
        E_charge[v].append((u, 1))
charge = floyd_warshall(E_charge)

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

Buggy python submission (verdict: Runtime Error):
from itertools import product, combinations

INF = float('inf')
def floyd_warshall(E):
    N = len(E)
    dist = [[INF for _ in range(N)] for _ in range(N)]
    for v in V:
        dist[v][v] = 0
        for u, c in E[v]: dist[v][u] = c
    for k in V:        
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

N, M, L = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1].append((b-1, c))
    E[b-1].append((a-1, c))
dist = floyd_warshall(V, E)

E_charge = [[] for _ in V]
for u, v in combinations(V, 2):
    if dist[u][v] <= L:
        E_charge[u].append((v, 1))
        E_charge[v].append((u, 1))
charge = floyd_warshall(V, E_charge)

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

Fixed submission:
from itertools import product, combinations

INF = float('inf')
def floyd_warshall(E):
    N = len(E)
    dist = [[INF for _ in range(N)] for _ in range(N)]
    for v in range(N):
        dist[v][v] = 0
        for u, c in E[v]: dist[v][u] = c
    for k in range(N):        
        for i, j in product(range(N), repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

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

E_charge = [[] for _ in range(N)]
for u, v in combinations(range(N), 2):
    if dist[u][v] <= L:
        E_charge[u].append((v, 1))
        E_charge[v].append((u, 1))
charge = floyd_warshall(E_charge)

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

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product, combinations

INF = float('inf')
def floyd_warshall(V, E):
    dist = [[INF for _ in V] for _ in V]
    for v in V:
        dist[v][v] = 0
        for u, c in E[v]: dist[v][u] = c
    for k in V:        
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

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

dist = floyd_warshall(V, E)
E_charge = [[] for _ in V]
for u, v in combinations(V, 2):
    if dist[u][v] <= L:
        E_charge[u].append((v, 1))
        E_charge[v].append((u, 1))
charge = floyd_warshall(V, E_charge)

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

Fixed submission:
from itertools import product, combinations

INF = float('inf')
def floyd_warshall(E):
    N = len(E)
    dist = [[INF for _ in range(N)] for _ in range(N)]
    for v in range(N):
        dist[v][v] = 0
        for u, c in E[v]: dist[v][u] = c
    for k in range(N):        
        for i, j in product(range(N), repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

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

E_charge = [[] for _ in range(N)]
for u, v in combinations(range(N), 2):
    if dist[u][v] <= L:
        E_charge[u].append((v, 1))
        E_charge[v].append((u, 1))
charge = floyd_warshall(E_charge)

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

Buggy python submission (verdict: Runtime Error):
from itertools import product, combinations

INF = float('inf')
def floyd_warshall(V, E):
    dist = {u: {v: INF for v in V} for u in V}
    for v in V:
        dist[v][v] = 0
        for u, c in E[v]: dist[v][u] = c
    for k in V:        
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

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

dist = floyd_warshall(V, E)
E_charge = [[] for _ in V]
for u, v in combinations(V, 2):
    if dist[u][v] <= L: E_charge[u][v] = 1; E_charge[v][u] = 1;
charge = floyd_warshall(V, E_charge)

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

Fixed submission:
from itertools import product, combinations

INF = float('inf')
def floyd_warshall(E):
    N = len(E)
    dist = [[INF for _ in range(N)] for _ in range(N)]
    for v in range(N):
        dist[v][v] = 0
        for u, c in E[v]: dist[v][u] = c
    for k in range(N):        
        for i, j in product(range(N), repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

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

E_charge = [[] for _ in range(N)]
for u, v in combinations(range(N), 2):
    if dist[u][v] <= L:
        E_charge[u].append((v, 1))
        E_charge[v].append((u, 1))
charge = floyd_warshall(E_charge)

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

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product, combinations

INF = float('inf')
def floyd_warshall(V, E):
    dist = {u: {v: INF for v in V} for u in V}
    for v in V:
        dist[v][v] = 0
        for u, c in E[v].items(): dist[v][u] = c
    for k in V:        
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

N, M, L = map(int, input().split())
V = list(range(N))
E = {v: {} for v in V}
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = c
    E[b-1][a-1] = c

dist = floyd_warshall(V, E)
E_charge = {v: {} for v in V}
for u, v in combinations(V, 2):
    if dist[u][v] <= L: E_charge[u][v] = 1; E_charge[v][u] = 1;
charge = floyd_warshall(V, E_charge)

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

Fixed submission:
from itertools import product, combinations

INF = float('inf')
def floyd_warshall(E):
    N = len(E)
    dist = [[INF for _ in range(N)] for _ in range(N)]
    for v in range(N):
        dist[v][v] = 0
        for u, c in E[v]: dist[v][u] = c
    for k in range(N):        
        for i, j in product(range(N), repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

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

E_charge = [[] for _ in range(N)]
for u, v in combinations(range(N), 2):
    if dist[u][v] <= L:
        E_charge[u].append((v, 1))
        E_charge[v].append((u, 1))
charge = floyd_warshall(E_charge)

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

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from itertools import product, combinations

INF = float('inf')
def floyd_warshall(V, E):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
    Output:
        If there exists a negative cycle, return (None, prev), where prev is
        the table, whose (i, j)-element is the previous vertices in the shortest (i, j)-path
        Otherwise return (dist, prev), where dist is the table of the minimum cost
        between arbitrary vertex u, v in the given graph
    '''
    dist = {u: {v: INF for v in V} for u in V}
    prev = {u: {v: None for v in V} for u in V}
    for v in V:
        dist[v][v] = 0; prev[v][v] = -1
        for u, c in E[v].items(): dist[v][u] = c; prev[v][u] = v;
    for k in V:        
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
                prev[i][j] = prev[k][j]
    for v in V:
        if dist[v][v] < 0: return None, prev
    return dist, prev

N, M, L = map(int, input().split())
V = list(range(N))
E = defaultdict(dict)
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = c
    E[b-1][a-1] = c

dist, _ = floyd_warshall(V, E)
E_charge = defaultdict(dict)
for u, v in combinations(V, 2):
    if dist[u][v] <= L: E_charge[u][v] = 1; E_charge[v][u] = 1;
charge, _ = floyd_warshall(V, E_charge)

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

Fixed submission:
from itertools import product, combinations

INF = float('inf')
def floyd_warshall(E):
    N = len(E)
    dist = [[INF for _ in range(N)] for _ in range(N)]
    for v in range(N):
        dist[v][v] = 0
        for u, c in E[v]: dist[v][u] = c
    for k in range(N):        
        for i, j in product(range(N), repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

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

E_charge = [[] for _ in range(N)]
for u, v in combinations(range(N), 2):
    if dist[u][v] <= L:
        E_charge[u].append((v, 1))
        E_charge[v].append((u, 1))
charge = floyd_warshall(E_charge)

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