Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
from collections import deque
from array import array

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

# diagonal square matrix for pypy

class DiagonalMatrix:
    def __init__(self, size):
        self._size = size
        array_size = (size+1)*size//2
        # 三角行列の要素を1次元配列に並べる
        self._storage = array('l', [0]*array_size)

    def _index(self, i, j):
        _n = self._size
        _i = i+1
        _j = j+1
        return (_n+1)*_n//2 - (_n-_i+2)*(_n-_i+1)//2 + (_j-_i+1) - 1
    
    def get(self,i,j):
        if i <= j:
            return self._storage[self._index(i,j)]
        else:
            return self._storage[self._index(j,i)]

    def set(self, i, j, value):
        if i <= j:
            self._storage[self._index(i,j)] = value
        else:
            self._storage[self._index(j,i)] = value
        
'''
N = 5
matrix = DiagonalMatrix(N)
for i in range(N):
    for j in range(i,N):
        matrix.set(i,j,matrix._index(i,j))
        print(i,j,matrix._index(i,j),matrix._storage)

for i in range(N):
    print([matrix.get(i,j) for j in range(N)])
'''
    
##### main

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

C = DiagonalMatrix(N)

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

Q = int(input())

#S = array('q', [0]*Q)
#T = array('q', [0]*Q)
#S = [0]*Q
#T = [0]*Q
#ST = {}
ST = [None]*Q

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

# ワーシャルフロイド法

# distance from i to j
#D = [array('q', [0]*N) for i in range(N)]
D = DiagonalMatrix(N)

# initialization
for i in range(N):
    for j in range(i+1,N):
        c = C.get(i,j)
        if c == 0:
            D.set(i,j,sys.maxsize)
        else:
            D.set(i,j,c)

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(i+1,N):
            if D.get(i,j) > D.get(i,k) + D.get(k,j):
                D.set(i,j, D.get(i,k) + D.get(k,j))

'''
fo i in range(N):
    print([D.get(i,j) for j in range(N)])
'''


#sys.exit()

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

# ワーシャルフロイド法 again

# distance from i to j
D = DiagonalMatrix(N)
STEP = DiagonalMatrix(N)

# initialization
for i in range(N):
    for j in range(i+1,N):
        c = C.get(i,j)
        if c == 0:
            D.set(i,j,sys.maxsize)
            STEP.set(i,j,sys.maxsize)
        else:
            D.set(i,j,c)
            STEP.set(i,j,1)

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(i+1,N):
            if D.get(i,j) > D.get(i,k) + D.get(k,j):
                D.set(i,j, D.get(i,k) + D.get(k,j))
                STEP.set(i,j, STEP.get(i,k) + STEP.get(k,j))

# answer
for q in range(Q):
    i,j = ST[q]
    step = STEP.get(i,j)
    if step == sys.maxsize:
        print(-1)
    else:
        print(step-1)


Fixed submission:
#!/usr/bin/python3
# -*- 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))

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
from collections import deque
from array import array

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

# diagonal square matrix for pypy

class DiagonalMatrix:
    def __init__(self, size):
        self._size = size
        array_size = (size+1)*size//2
        # 三角行列の要素を1次元配列に並べる
        self._storage = array('l', [0]*array_size)

    def _index(self, i, j):
        _n = self._size
        _i = i+1
        _j = j+1
        return (_n+1)*_n//2 - (_n-_i+2)*(_n-_i+1)//2 + (_j-_i+1) - 1
    
    def get(self,i,j):
        if i <= j:
            return self._storage[self._index(i,j)]
        else:
            return self._storage[self._index(j,i)]

    def set(self, i, j, value):
        if i <= j:
            self._storage[self._index(i,j)] = value
        else:
            self._storage[self._index(j,i)] = value
        
'''
N = 5
matrix = DiagonalMatrix(N)
for i in range(N):
    for j in range(i,N):
        matrix.set(i,j,matrix._index(i,j))
        print(i,j,matrix._index(i,j),matrix._storage)

for i in range(N):
    print([matrix.get(i,j) for j in range(N)])
'''
    
##### main

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

C = DiagonalMatrix(N)

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

Q = int(input())

#S = array('q', [0]*Q)
#T = array('q', [0]*Q)
#S = [0]*Q
#T = [0]*Q
#ST = {}
ST = [None]*Q

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

# ワーシャルフロイド法

# distance from i to j
#D = [array('q', [0]*N) for i in range(N)]
D = DiagonalMatrix(N)

# initialization
for i in range(N):
    for j in range(i,N):
        c = C.get(i,j)
        if c == 0:
            D.set(i,j,sys.maxsize)
        else:
            D.set(i,j,c)

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(i,N):
            if D.get(i,j) > D.get(i,k) + D.get(k,j):
                D.set(i,j, D.get(i,k) + D.get(k,j))

'''
fo i in range(N):
    print([D.get(i,j) for j in range(N)])
'''
    
# D[i][j] <= L となる i,j に辺を張る
for i in range(N):
    for j in range(i,N):
        if D.get(i,j) <= L:
            C.set(i,j,1)

# ワーシャルフロイド法 again

# distance from i to j
D = DiagonalMatrix(N)
STEP = DiagonalMatrix(N)

# initialization
for i in range(N):
    for j in range(i,N):
        c = C.get(i,j)
        if c == 0:
            D.set(i,j,sys.maxsize)
            STEP.set(i,j,sys.maxsize)
        else:
            D.set(i,j,c)
            STEP.set(i,j,1)

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(i,N):
            if D.get(i,j) > D.get(i,k) + D.get(k,j):
                D.set(i,j, D.get(i,k) + D.get(k,j))
                STEP.set(i,j, STEP.get(i,k) + STEP.get(k,j))

# answer
for q in range(Q):
    i,j = ST[q]
    step = STEP.get(i,j)
    if step == sys.maxsize:
        print(-1)
    else:
        print(step-1)


Fixed submission:
#!/usr/bin/python3
# -*- 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))

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
from collections import deque
from array import array

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

# diagonal square matrix for pypy
class DiagonalMatrix:
    def __init__(self, size):
        self._size = size
        array_size = (size+1)*size//2
        self._storage = array('l', [0]*array_size)

    def _index(self, i, j):
        _n = self._size
        _i = i+1
        _j = j+1
        return (_n+1)*_n//2 - (_n-_i+2)*(_n-_i+1)//2 + (_j-_i+1) - 1
    
    def get(self,i,j):
        if i <= j:
            return self._storage[self._index(i,j)]
        else:
            return self._storage[self._index(j,i)]

    def set(self, i, j, value):
        if i <= j:
            self._storage[self._index(i,j)] = value
        else:
            self._storage[self._index(j,i)] = value
        
'''
N = 5
matrix = DiagonalMatrix(N)
for i in range(N):
    for j in range(i,N):
        matrix.set(i,j,matrix._index(i,j))
        print(i,j,matrix._index(i,j),matrix._storage)

for i in range(N):
    print([matrix.get(i,j) for j in range(N)])
'''
    
##### main

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

C = DiagonalMatrix(N)

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

Q = int(input())

#S = array('q', [0]*Q)
#T = array('q', [0]*Q)
#S = [0]*Q
#T = [0]*Q
#ST = {}
ST = [None]*Q

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

# ワーシャルフロイド法

# distance from i to j
#D = [array('q', [0]*N) for i in range(N)]
D = DiagonalMatrix(N)

# initialization
for i in range(N):
    for j in range(N):
        c = C.get(i,j)
        if c == 0:
            D.set(i,j,sys.maxsize)
        else:
            D.set(i,j,c)

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D.get(i,j) > D.get(i,k) + D.get(k,j):
                D.set(i,j, D.get(i,k) + D.get(k,j))

'''
fo i in range(N):
    print([D.get(i,j) for j in range(N)])
'''
    
# D[i][j] <= L となる i,j に辺を張る
for i in range(N):
    for j in range(N):
        if D.get(i,j) <= L:
            C.set(i,j,1)

# ワーシャルフロイド法 again

# distance from i to j
D = DiagonalMatrix(N)
STEP = DiagonalMatrix(N)

# initialization
for i in range(N):
    for j in range(i,N):
        c = C.get(i,j)
        c = C.get(i,j)
        if c == 0:
            D.set(i,j,sys.maxsize)
            STEP.set(i,j,sys.maxsize)
        else:
            D.set(i,j,c)
            STEP.set(i,j,1)

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D.get(i,j) > D.get(i,k) + D.get(k,j):
                D.set(i,j, D.get(i,k) + D.get(k,j))
                STEP.set(i,j, STEP.get(i,k) + STEP.get(k,j))

# answer
for q in range(Q):
    i,j = ST[q]
    step = STEP.get(i,j)
    if step == sys.maxsize:
        print(-1)
    else:
        print(step-1)


Fixed submission:
#!/usr/bin/python3
# -*- 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))

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
from collections import deque
from array import array

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

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

_C = {}

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

def C_(i,j):
    return _C.get(i*300+j, sys.maxsize)

Q = int(input())

#S = array('q', [0]*Q)
#T = array('q', [0]*Q)
#S = [0]*Q
#T = [0]*Q
ST = {}

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

# ワーシャルフロイド法

# distance from i to j
#D = [array('q', [0]*N) for i in range(N)]
D = [[0]*N for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        D[i][j] = C_(i,j)
        #print(i,j,D[i][j])

# 本計算
for k in range(N):
    Dk = D[k]
    for i in range(N):
        Di = D[i]
        for j in range(N):
            #if D[i][j] > D[i][k] + D[k][j]:
                #D[i][j] = D[i][k] + D[k][j]
            if Di[j] > Di[k] + Dk[j]:
                Di[j] = Di[k] + Dk[j]


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

# ワーシャルフロイド法 again

# distance from i to j
#D = [array('q', [0]*N) for i in range(N)]
D = [[0]*N for i in range(N)]
#STEP = [array('q', [0]*N) for i in range(N)]
STEP = [[0]*N for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        c = C_(i,j)
        D[i][j] = c
        if c == sys.maxsize:
            STEP[i][j] = sys.maxsize
        else:
            STEP[i][j] = 1
        #print(i,j,D[i][j],STEP[i][j])

# 本計算
for k in range(N):
    Dk = D[k]
    STEPk = STEP[k]
    for i in range(N):
        Di = D[i]
        STEPi = STEP[i]
        for j in range(N):
            if Di[j] > Di[k] + Dk[j]:
                Di[j] = Di[k] + Dk[j]
                STEPi[j] = STEPi[k] + STEPk[j]


# answer
for q in range(Q):
    i,j = ST[q]
    step = STEP[i][j]
    if step == sys.maxsize:
        #print(i,j,-1)
        print(-1)
    else:
        print(step-1)


Fixed submission:
#!/usr/bin/python3
# -*- 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))

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
from collections import deque
from array import array

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

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

_C = {}

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

def C_(i,j):
    return _C.get(i*300+j, sys.maxsize)

Q = int(input())

#S = array('q', [0]*Q)
#T = array('q', [0]*Q)
S = [0]*Q
T = [0]*Q

for i in range(Q):
    S[i],T[i] = list(map(int, input().split()))

# ワーシャルフロイド法

# distance from i to j
#D = [array('q', [0]*N) for i in range(N)]
D = [[0]*N for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        D[i][j] = C_(i,j)
        #print(i,j,D[i][j])

# 本計算
for k in range(N):
    Dk = D[k]
    for i in range(N):
        Di = D[i]
        for j in range(N):
            #if D[i][j] > D[i][k] + D[k][j]:
                #D[i][j] = D[i][k] + D[k][j]
            if Di[j] > Di[k] + Dk[j]:
                Di[j] = Di[k] + Dk[j]


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

# ワーシャルフロイド法 again

# distance from i to j
#D = [array('q', [0]*N) for i in range(N)]
D = [[0]*N for i in range(N)]
#STEP = [array('q', [0]*N) for i in range(N)]
STEP = [[0]*N for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        c = C_(i,j)
        D[i][j] = c
        if c == sys.maxsize:
            STEP[i][j] = sys.maxsize
        else:
            STEP[i][j] = 1
        #print(i,j,D[i][j],STEP[i][j])

# 本計算
for k in range(N):
    Dk = D[k]
    STEPk = STEP[k]
    for i in range(N):
        Di = D[i]
        STEPi = STEP[i]
        for j in range(N):
            if Di[j] > Di[k] + Dk[j]:
                Di[j] = Di[k] + Dk[j]
                STEPi[j] = STEPi[k] + STEPk[j]


# answer
for q in range(Q):
    i = S[q]-1
    j = T[q]-1
    step = STEP[i][j]
    if step == sys.maxsize:
        #print(i,j,-1)
        print(-1)
    else:
        print(step-1)


Fixed submission:
#!/usr/bin/python3
# -*- 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))

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
from collections import deque
from array import array

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

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

_C = {}

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

def C_(i,j):
    return _C.get(i*300+j, sys.maxsize)

Q = int(input())

#S = array('q', [0]*Q)
#T = array('q', [0]*Q)
S = [0]*Q
T = [0]*Q

for i in range(Q):
    S[i],T[i] = list(map(int, input().split()))

# ワーシャルフロイド法

# distance from i to j
#D = [array('q', [0]*N) for i in range(N)]
D = [[0]*N for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        D[i][j] = C_(i,j)
        #print(i,j,D[i][j])

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][j] > D[i][k] + D[k][j]:
                D[i][j] = D[i][k] + D[k][j]


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

# ワーシャルフロイド法 again

# distance from i to j
#D = [array('q', [0]*N) for i in range(N)]
D = [[0]*N for i in range(N)]
#STEP = [array('q', [0]*N) for i in range(N)]
STEP = [[0]*N for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        c = C_(i,j)
        D[i][j] = c
        if c == sys.maxsize:
            STEP[i][j] = sys.maxsize
        else:
            STEP[i][j] = 1
        #print(i,j,D[i][j],STEP[i][j])

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][j] > D[i][k] + D[k][j]:
                D[i][j] = D[i][k] + D[k][j]
                STEP[i][j] = STEP[i][k] + STEP[k][j]


# answer
for q in range(Q):
    i = S[q]-1
    j = T[q]-1
    step = STEP[i][j]
    if step == sys.maxsize:
        #print(i,j,-1)
        print(-1)
    else:
        print(step-1)


Fixed submission:
#!/usr/bin/python3
# -*- 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))

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
from collections import deque
from array import array

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

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

_C = {}

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

def C_(i,j):
    return _C.get(i*300+j, sys.maxsize)

Q = int(input())

S = array('q', [0]*Q)
T = array('q', [0]*Q)

for i in range(Q):
    S[i],T[i] = list(map(int, input().split()))

# ワーシャルフロイド法

# distance from i to j
D = [array('q', [0]*N) for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        D[i][j] = C_(i,j)
        #print(i,j,D[i][j])

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][j] > D[i][k] + D[k][j]:
                D[i][j] = D[i][k] + D[k][j]


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

# ワーシャルフロイド法 again

# distance from i to j
D = [array('q', [0]*N) for i in range(N)]
STEP = [array('q', [0]*N) for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        c = C_(i,j)
        D[i][j] = c
        if c == sys.maxsize:
            STEP[i][j] = sys.maxsize
        else:
            STEP[i][j] = 1
        #print(i,j,D[i][j],STEP[i][j])

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][j] > D[i][k] + D[k][j]:
                D[i][j] = D[i][k] + D[k][j]
                STEP[i][j] = STEP[i][k] + STEP[k][j]


# answer
for q in range(Q):
    i = S[q]-1
    j = T[q]-1
    step = STEP[i][j]
    if step == sys.maxsize:
        #print(i,j,-1)
        print(-1)
    else:
        print(step-1)


Fixed submission:
#!/usr/bin/python3
# -*- 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))

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
from collections import deque
from array import array

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

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

_C = {}

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

def C_(i,j):
    return _C.get(i*300+j, sys.maxsize)

Q = int(input())

S = array('q', [0]*Q)
T = array('q', [0]*Q)

for i in range(Q):
    S[i],T[i] = list(map(int, input().split()))

# ワーシャルフロイド法

# distance from i to j
D = [array('q', [0]*N) for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        D[i][j] = C_(i,j)
        #print(i,j,D[i][j])

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][j] > D[i][k] + D[k][j]:
                D[i][j] = D[i][k] + D[k][j]


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

# ワーシャルフロイド法 again

# distance from i to j
D = [array('q', [0]*N) for i in range(N)]
STEP = [array('q', [0]*N) for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        c = C_(i,j)
        D[i][j] = c
        if c == sys.maxsize:
            STEP[i][j] = sys.maxsize
        else:
            STEP[i][j] = 1
        #print(i,j,D[i][j],STEP[i][j])

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][j] > D[i][k] + D[k][j]:
                D[i][j] = D[i][k] + D[k][j]
                STEP[i][j] = STEP[i][k] + STEP[k][j]


# answer
for q in range(Q):
    i = S[q]-1
    j = T[q]-1
    step = STEP[i][j]
    if step == sys.maxsize:
        #print(i,j,-1)
        print(-1)
    else:
        print(step-1)


Fixed submission:
#!/usr/bin/python3
# -*- 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))