Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import heapq
import sys
input = sys.stdin.readline

f=lambda:map(int,input().split())
V,E,L=f()
G=[[] for _ in [0]*(V+1)]
# G=[]

for _ in range(E):
    s,t,d=f()
    if d<=L:
        G[s].append((t,d))
        G[t].append((s,d))

INF=V+5

res=[[(INF,0)]*(V+1) for _ in  [0]*(V+1)]

for start in range(1,V+1):
    q=[((0,0),start)]
    while q:
        c,town=heapq.heappop(q)
        if res[start][town]<c:
            continue
        h,cost=c
        for next_town,d in G[town]:
            D=cost+d
            if D<=L and (h,D)<res[start][next_town]:
                heapq.heappush(q,((h,D),next_town))
                res[start][next_town]=(h,D)
            elif D>L and (1+h,d)<res[start][next_town]:
                heapq.heappush(q,((1+h,d),next_town))
                res[start][next_town]=(1+h,d)

Q=int(input())
for _ in [0]*Q:
    s,t=f()
    r=res[s][t][0]
    print(r if r<INF else -1)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import heapq
import sys
input = sys.stdin.readline

f=lambda:map(int,input().split())
V,E,L=f()
G=[[] for _ in [0]*(V+1)]
# G=[]

for _ in range(E):
    s,t,d=f()
    if d<=L:
        G[s].append((t,d))
        G[t].append((s,d))

INF=V+5

res=[[(INF,0)]*(V+1) for _ in  [0]*(V+1)]

for start in range(1,V+1):
    q=[((0,0),start)]
    while q:
        c,town=heapq.heappop(q)
        if c<res[start][town]:
            res[start][town]=c
        else:
            continue
        h,cost=c
        for next_town,d in G[town]:
            D=cost+d
            if D<=L and (h,D)<res[start][next_town]:
                heapq.heappush(q,((h,D),next_town))
            elif D>L and (1+h,d)<res[start][next_town]:
                heapq.heappush(q,((1+h,d),next_town))

Q=int(input())
for _ in [0]*Q:
    s,t=f()
    r=res[s][t][0]
    print(r if r<INF else -1)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import heapq
import sys
input = sys.stdin.readline

f=lambda:map(int,input().split())
V,E,L=f()
G=[[] for _ in [0]*(V+1)]
# G=[]

for _ in range(E):
    s,t,d=f()
    if d<=L:
        G[s].append((t,(0,d)))
        G[t].append((s,(0,d)))
    
INF=V+5

res=[[(INF,0)]*(V+1) for _ in  [0]*(V+1)]

for s in range(V):
    # q[i]:点i+1の現状のコスト
    q=[((0,0),s+1)]
    heapq.heapify(q)
    while q:
        C,p=heapq.heappop(q)
        if C<res[s+1][p]:
            res[s+1][p]=C
        else:
            continue
        for np,D in G[p]:
            d=D[1]+C[1]
            if d>L:
                costB=(1+C[0]+D[0],D[1])
            else:
                costB=(C[0]+D[0],d)
            heapq.heappush(q,(min(res[s+1][np],costB),np))



Q=int(input())
for _ in [0]*Q:
    s,t=f()
    r=res[s][t][0]
    print(r if r<INF else -1)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import heapq
import sys
input = sys.stdin.readline

f=lambda:map(int,input().split())
V,E,L=f()
G=[[] for _ in [0]*(V+1)]
# G=[]

for _ in range(E):
    s,t,d=f()
    if d<=L:
        G[s].append((t,(0,d)))
        G[t].append((s,(0,d)))
    
INF=10**15

def dijk(s):
    # q[i]:点i+1の現状のコスト
    q=[((0,0),s)]
    heapq.heapify(q)

    res=[(INF,INF)]*(V+1)
    while q:
        C,p=heapq.heappop(q)
        if C<res[p]:
            res[p]=C
        else:
            continue
        for np,D in G[p]:
            d=D[1]+C[1]
            if d>L:
                costB=(1+C[0]+D[0],D[1])
            else:
                costB=(C[0]+D[0],d)
            heapq.heappush(q,(min(res[np],costB),np))
    return res

res=[0]+[dijk(i+1) for i in range(V)]

Q=int(input())
for _ in [0]*Q:
    s,t=f()
    r=res[s][t][0]
    print(r if r<INF else -1)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
f=lambda:map(int,input().split())
V,E,L=f()
G=[[] for _ in [0]*(V+1)]
# G=[]

for _ in range(E):
    s,t,d=f()
    if d<=L:
        G[s].append((t,(0,d)))
        G[t].append((s,(0,d)))
    
INF=10**15

def dijk(s):
    # q[i]:点i+1の現状のコスト
    q=[((0,0),s)]
    heapq.heapify(q)

    res=[(INF,INF)]*(V+1)
    while q:
        C,p=heapq.heappop(q)
        if C<res[p]:
            res[p]=C
        else:
            continue
        for np,D in G[p]:
            d=D[1]+C[1]
            if d>L:
                costB=(1+C[0]+D[0],D[1])
            else:
                costB=(C[0]+D[0],d)
            heapq.heappush(q,(min(res[np],costB),np))
    return res

res=[0]+[dijk(i+1) for i in range(V)]

Q=int(input())
for _ in [0]*Q:
    s,t=f()
    r=res[s][t][0]
    print(r if r<INF else -1)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
f=lambda:map(int,input().split())
V,E,L=f()
G=[[] for _ in [0]*(V+1)]
# G=[]

for _ in range(E):
    s,t,d=f()
    if d<=L:
        G[s].append((t,(0,d)))
        G[t].append((s,(0,d)))
    
INF=float('inf')

def dijk(s):
    q=[((INF,INF),i) for i in range(V+1)]
    # q[i]:点i+1の現状のコスト
    q[s]=((0,0),s)
    heapq.heapify(q)

    res=[(INF,INF)]*(V+1)
    while q:
        C,p=heapq.heappop(q)
        if C<res[p]:
            res[p]=C
        else:
            continue
        for np,D in G[p]:
            costA=res[np]
            d=D[1]+C[1]
            if d>L:
                costB=(1+C[0]+D[0],D[1])
            else:
                costB=(C[0]+D[0],d)
            heapq.heappush(q,(min(costA,costB),np))
    return res

res=[0]+[dijk(i+1) for i in range(V)]

Q=int(input())
for _ in [0]*Q:
    s,t=f()
    r=res[s][t][0]
    print(r if r<INF else -1)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
f=lambda:map(int,input().split())
V,E,L=f()
G=[[] for _ in [0]*(V+1)]
# G=[]

for _ in range(E):
    s,t,d=f()
    if d<=L:
        G[s].append((t,(0,d)))
        G[t].append((s,(0,d)))
    
INF=float('inf')

def dijk(s,t):
    q=[((INF,INF),i) for i in range(V+1)]
    # q[i]:点i+1の現状のコスト
    q[s]=((0,0),s)
    heapq.heapify(q)

    res=[(INF,INF)]*(V+1)
    while q:
        C,p=heapq.heappop(q)
        if C<res[p]:
            res[p]=C
        else:
            continue
        if p==t:
            break
        for np,D in G[p]:
            costA=res[np]
            d=D[1]+C[1]
            if d>L:
                costB=(1+C[0]+D[0],D[1])
            else:
                costB=(C[0]+D[0],d)
            heapq.heappush(q,(min(costA,costB),np))
    return res[t][0] if res[t][0]<INF else -1

Q=int(input())
for _ in [0]*Q:
    s,t=f()
    print(dijk(s,t))

Fixed submission:
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)