Buggy python submission (verdict: Time Limit Exceeded):
#import sys
import heapq
#from collections import deque
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False
BIG = 1234567890

def ddprint(x):
  if DBG:
    print(x)

n,m,l = inm()

distance = [ [BIG] * n for i in range(n) ]
hops = [ [(BIG,0)] * n for i in range(n) ]
for i in range(n):
  distance[i][i] = 0
  hops[i][i] = (0,0)

dst = [ [] for i in range(n) ]
for i in range(m):
  a,b,c = inm()
  if c>l:
    continue
  a -= 1
  b -= 1
  distance[a][b] = distance[b][a] = c
  dst[a].append(b)
  dst[b].append(a)

for i in range(n):
  #for j in range(n):
  #  if j==i:
  #    continue
  #  if hops[i][j] > hops[j][i]:
  #    hops[i][j] = hops[j][i]

  #q = deque([ (x,(0,distance[i][x])) for x in dst[i] ])
  q = [ ((0,distance[i][x]), x) for x in dst[i] ]
  heapq.heapify(q)
  while len(q)>0:
    #y,e = q.popleft()
    e,y = heapq.heappop(q)
    #ddprint("y {} e {} {}".format(y,e[0],e[1]))
    if e>=hops[i][y]:
      continue
    #ddprint("upd i {} y {}".format(i,y))
    hops[i][y] = e
    for f in dst[y]:
      ds = distance[y][f]
      #ddprint("y {} f {} ds {}".format(y,f,ds))
      if e[1]+ds > l:
        newd = (e[0]+1, ds)
      else:
        newd = (e[0], e[1]+ds)
      if newd < hops[i][f]:
        heapq.heappush(q,(newd,f))
        #q.append((f,newd))

if DBG:
  for i in range(n):
    print(hops[i])

B2 = BIG//2
#for i in range(n):
#  for j in range(n):
#    if hops[i][j][0] > B2:
#      hops[i][j] = (-1,0)

p = inn()
for i in range(p):
  s,t = inm()
  #ddprint("q {} s {} t {}".format(i,s,t))
  x = hops[s-1][t-1][0]
  print(x if x<B2 else -1)


Fixed submission:
import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 9999999999

def ddprint(x):
  if DBG:
    print(x)

def ws(dist):
    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])

n,m,l = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b,c = inm()
    dst[a-1].append((b-1,c))
    dst[b-1].append((a-1,c))

dist1 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist1[i][i] = 0
    for j,c in dst[i]:
        dist1[i][j] = c

ws(dist1)

dist2 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist2[i][i] = 0
    for j in range(n):
        if dist1[i][j] <= l:
            dist2[i][j] = 1

ws(dist2)

q = inn()
for i in range(q):
    s,t = inm()
    d = dist2[s-1][t-1]
    print(d-1 if d<BIG else -1)

Buggy python submission (verdict: Time Limit Exceeded):
#import sys
from collections import deque
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False
BIG = 1234567890

def ddprint(x):
  if DBG:
    print(x)

n,m,l = inm()

distance = [ [BIG] * n for i in range(n) ]
hops = [ [(BIG,0)] * n for i in range(n) ]
for i in range(n):
  distance[i][i] = 0
  hops[i][i] = (0,0)

dst = [ [] for i in range(n) ]
for i in range(m):
  a,b,c = inm()
  if c>l:
    continue
  a -= 1
  b -= 1
  distance[a][b] = distance[b][a] = c
  dst[a].append(b)
  dst[b].append(a)

for i in range(n):
  q = deque([ (x,(0,distance[i][x])) for x in dst[i] ])
  while len(q)>0:
    y,e = q.popleft()
    #ddprint("y {} e {} {}".format(y,e[0],e[1]))
    if e>=hops[i][y]:
      continue
    #ddprint("upd i {} y {}".format(i,y))
    hops[i][y] = e
    for f in dst[y]:
      ds = distance[y][f]
      #ddprint("y {} f {} ds {}".format(y,f,ds))
      if e[1]+ds > l:
        newd = (e[0]+1, ds)
      else:
        newd = (e[0], e[1]+ds)
      if newd < hops[i][f]:
        q.append((f,newd))

if DBG:
  for i in range(n):
    print(hops[i])

B2 = BIG//2
#for i in range(n):
#  for j in range(n):
#    if hops[i][j][0] > B2:
#      hops[i][j] = (-1,0)

p = inn()
for i in range(p):
  s,t = inm()
  #ddprint("q {} s {} t {}".format(i,s,t))
  x = hops[s-1][t-1][0]
  print(x if x<B2 else -1)


Fixed submission:
import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 9999999999

def ddprint(x):
  if DBG:
    print(x)

def ws(dist):
    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])

n,m,l = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b,c = inm()
    dst[a-1].append((b-1,c))
    dst[b-1].append((a-1,c))

dist1 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist1[i][i] = 0
    for j,c in dst[i]:
        dist1[i][j] = c

ws(dist1)

dist2 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist2[i][i] = 0
    for j in range(n):
        if dist1[i][j] <= l:
            dist2[i][j] = 1

ws(dist2)

q = inn()
for i in range(q):
    s,t = inm()
    d = dist2[s-1][t-1]
    print(d-1 if d<BIG else -1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False
BIG = 1234567890

def ddprint(x):
  if DBG:
    print(x)

n,m,l = inm()

distance = [ [BIG] * n for i in range(n) ]
hops = [ [(BIG,0)] * n for i in range(n) ]
for i in range(n):
  distance[i][i] = 0
  hops[i][i] = (0,0)

dst = [ [] for i in range(n) ]
for i in range(m):
  a,b,c = inm()
  if c>l:
    continue
  a -= 1
  b -= 1
  distance[a][b] = distance[b][a] = c
  dst[a].append(b)
  dst[b].append(a)

for i in range(n):
  q = deque([ (x,(0,distance[i][x])) for x in dst[i] ])
  while len(q)>0:
    y,e = q.popleft()
    #ddprint("y {} e {} {}".format(y,e[0],e[1]))
    if e>=hops[i][y]:
      continue
    #ddprint("upd i {} y {}".format(i,y))
    hops[i][y] = e
    for f in dst[y]:
      ds = distance[y][f]
      #ddprint("y {} f {} ds {}".format(y,f,ds))
      if e[1]+ds > l:
        newd = (e[0]+1, ds)
      else:
        newd = (e[0], e[1]+ds)
      if newd < hops[i][f]:
        q.append((f,newd))

if DBG:
  for i in range(n):
    print(hops[i])

B2 = BIG//2
#for i in range(n):
#  for j in range(n):
#    if hops[i][j][0] > B2:
#      hops[i][j] = (-1,0)

p = inn()
for i in range(p):
  s,t = inm()
  #ddprint("q {} s {} t {}".format(i,s,t))
  x = hops[s-1][t-1][0]
  print(x if x<B2 else -1)


Fixed submission:
import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 9999999999

def ddprint(x):
  if DBG:
    print(x)

def ws(dist):
    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])

n,m,l = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b,c = inm()
    dst[a-1].append((b-1,c))
    dst[b-1].append((a-1,c))

dist1 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist1[i][i] = 0
    for j,c in dst[i]:
        dist1[i][j] = c

ws(dist1)

dist2 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist2[i][i] = 0
    for j in range(n):
        if dist1[i][j] <= l:
            dist2[i][j] = 1

ws(dist2)

q = inn()
for i in range(q):
    s,t = inm()
    d = dist2[s-1][t-1]
    print(d-1 if d<BIG else -1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False
BIG = 1234567890

def ddprint(x):
  if DBG:
    print(x)

n,m,l = inm()

distance = [ [BIG] * n for i in range(n) ]
hops = [ [(BIG,0)] * n for i in range(n) ]
for i in range(n):
  distance[i][i] = 0
  hops[i][i] = (0,0)

dst = [ [] for i in range(n) ]
for i in range(m):
  a,b,c = inm()
  if c>l:
    continue
  a -= 1
  b -= 1
  distance[a][b] = distance[b][a] = c
  dst[a].append(b)
  dst[b].append(a)

for i in range(n):
  q = deque([ (x,(0,distance[i][x])) for x in dst[i] ])
  while len(q)>0:
    y,e = q.popleft()
    #ddprint("y {} e {} {}".format(y,e[0],e[1]))
    if e>=hops[i][y]:
      continue
    #ddprint("upd i {} y {}".format(i,y))
    hops[i][y] = e
    for f in dst[y]:
      ds = distance[y][f]
      #ddprint("y {} f {} ds {}".format(y,f,ds))
      if e[1]+ds > l:
        newd = (e[0]+1, ds)
      else:
        newd = (e[0], e[1]+ds)
      if newd < hops[i][f]:
        q.append((f,newd))

if DBG:
  for i in range(n):
    print(hops[i])

B2 = BIG//2
#for i in range(n):
#  for j in range(n):
#    if hops[i][j][0] > B2:
#      hops[i][j] = (-1,0)

p = inn()
for i in range(p):
  s,t = inm()
  #ddprint("q {} s {} t {}".format(i,s,t))
  x = hops[s-1][t-1][0]
  print(x if x<B2 else -1)


Fixed submission:
import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 9999999999

def ddprint(x):
  if DBG:
    print(x)

def ws(dist):
    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])

n,m,l = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b,c = inm()
    dst[a-1].append((b-1,c))
    dst[b-1].append((a-1,c))

dist1 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist1[i][i] = 0
    for j,c in dst[i]:
        dist1[i][j] = c

ws(dist1)

dist2 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist2[i][i] = 0
    for j in range(n):
        if dist1[i][j] <= l:
            dist2[i][j] = 1

ws(dist2)

q = inn()
for i in range(q):
    s,t = inm()
    d = dist2[s-1][t-1]
    print(d-1 if d<BIG else -1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False
BIG = 1234567890

def ddprint(x):
  if DBG:
    print(x)

n,m,l = inm()

distance = [ [BIG] * n for i in range(n) ]
hops = [ [(BIG,0)] * n for i in range(n) ]
for i in range(n):
  distance[i][i] = 0
  hops[i][i] = (0,0)

dst = [ [] for i in range(n) ]
for i in range(m):
  a,b,c = inm()
  a -= 1
  b -= 1
  if c>l:
    continue
  distance[a][b] = distance[b][a] = c
  dst[a].append(b)
  dst[b].append(a)

for i in range(n):
  d = (0,0)
  q = deque([ (x,(0,distance[i][x])) for x in dst[i] ])
  while len(q)>0:
    y,e = q.popleft()
    #ddprint("y {} e {} {}".format(y,e[0],e[1]))
    if e>=hops[i][y]:
      continue
    #ddprint("upd i {} y {}".format(i,y))
    hops[i][y] = e
    for f in dst[y]:
      ds = distance[y][f]
      #ddprint("y {} f {} ds {}".format(y,f,ds))
      if e[1]+ds > l:
        newd = (e[0]+1, ds)
      else:
        newd = (e[0], e[1]+ds)
      if newd < hops[i][f]:
        q.append((f,newd))

if DBG:
  for i in range(n):
    print(hops[i])

for i in range(n):
  for j in range(n):
    if hops[i][j][0] > BIG/2:
      hops[i][j] = (-1,0)

p = inn()
for i in range(p):
  s,t = inm()
  #ddprint("q {} s {} t {}".format(i,s,t))
  print(hops[s-1][t-1][0])


Fixed submission:
import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 9999999999

def ddprint(x):
  if DBG:
    print(x)

def ws(dist):
    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])

n,m,l = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b,c = inm()
    dst[a-1].append((b-1,c))
    dst[b-1].append((a-1,c))

dist1 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist1[i][i] = 0
    for j,c in dst[i]:
        dist1[i][j] = c

ws(dist1)

dist2 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist2[i][i] = 0
    for j in range(n):
        if dist1[i][j] <= l:
            dist2[i][j] = 1

ws(dist2)

q = inn()
for i in range(q):
    s,t = inm()
    d = dist2[s-1][t-1]
    print(d-1 if d<BIG else -1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False
BIG = 9876598765

def ddprint(x):
  if DBG:
    print(x)

n,m,l = inm()

distance = [ [BIG] * n for i in range(n) ]
hops = [ [(BIG,0)] * n for i in range(n) ]
for i in range(n):
  distance[i][i] = 0
  hops[i][i] = (0,0)

dst = [ [] for i in range(n) ]
for i in range(m):
  a,b,c = inm()
  a -= 1
  b -= 1
  if c>l:
    continue
  distance[a][b] = distance[b][a] = c
  dst[a].append(b)
  dst[b].append(a)

for i in range(n):
  d = (0,0)
  q = deque([ (x,(0,distance[i][x])) for x in dst[i] ])
  while len(q)>0:
    y,e = q.popleft()
    #ddprint("y {} e {} {}".format(y,e[0],e[1]))
    if e>=hops[i][y]:
      continue
    #ddprint("upd i {} y {}".format(i,y))
    hops[i][y] = e
    for f in dst[y]:
      ds = distance[y][f]
      #ddprint("y {} f {} ds {}".format(y,f,ds))
      if e[1]+ds > l:
        newd = (e[0]+1, ds)
      else:
        newd = (e[0], e[1]+ds)
      if newd < hops[i][f]:
        q.append((f,newd))

if DBG:
  for i in range(n):
    print(hops[i])

for i in range(n):
  for j in range(n):
    if hops[i][j][0] > BIG/2:
      hops[i][j] = (-1,0)

p = inn()
for i in range(p):
  s,t = inm()
  #ddprint("q {} s {} t {}".format(i,s,t))
  print(hops[s-1][t-1][0])


Fixed submission:
import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 9999999999

def ddprint(x):
  if DBG:
    print(x)

def ws(dist):
    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])

n,m,l = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b,c = inm()
    dst[a-1].append((b-1,c))
    dst[b-1].append((a-1,c))

dist1 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist1[i][i] = 0
    for j,c in dst[i]:
        dist1[i][j] = c

ws(dist1)

dist2 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist2[i][i] = 0
    for j in range(n):
        if dist1[i][j] <= l:
            dist2[i][j] = 1

ws(dist2)

q = inn()
for i in range(q):
    s,t = inm()
    d = dist2[s-1][t-1]
    print(d-1 if d<BIG else -1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False
BIG = 9876598765

def ddprint(x):
  if DBG:
    print(x)

n,m,l = inm()

distance = [ [BIG] * n for i in range(n) ]
hops = [ [(BIG,0)] * n for i in range(n) ]
for i in range(n):
  distance[i][i] = 0
  hops[i][i] = (0,0)

dst = [ [] for i in range(n) ]
for i in range(m):
  a,b,c = inm()
  a -= 1
  b -= 1
  if c>l:
    continue
  distance[a][b] = distance[b][a] = c
  dst[a].append(b)
  dst[b].append(a)

for i in range(n):
  d = (0,0)
  q = deque([ (x,(0,distance[i][x])) for x in dst[i] ])
  while len(q)>0:
    y,e = q.popleft()
    #ddprint("y {} e {} {}".format(y,e[0],e[1]))
    if e>=hops[i][y]:
      continue
    #ddprint("upd i {} y {}".format(i,y))
    hops[i][y] = e
    for f in dst[y]:
      ds = distance[y][f]
      #ddprint("y {} f {} ds {}".format(y,f,ds))
      if e[1]+ds > l:
        newd = (e[0]+1, ds)
      else:
        newd = (e[0], e[1]+ds)
      q.append((f,newd))

if DBG:
  for i in range(n):
    print(hops[i])

for i in range(n):
  for j in range(n):
    if hops[i][j][0] > BIG/2:
      hops[i][j] = (-1,0)

p = inn()
for i in range(p):
  s,t = inm()
  #ddprint("q {} s {} t {}".format(i,s,t))
  print(hops[s-1][t-1][0])


Fixed submission:
import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 9999999999

def ddprint(x):
  if DBG:
    print(x)

def ws(dist):
    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])

n,m,l = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b,c = inm()
    dst[a-1].append((b-1,c))
    dst[b-1].append((a-1,c))

dist1 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist1[i][i] = 0
    for j,c in dst[i]:
        dist1[i][j] = c

ws(dist1)

dist2 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist2[i][i] = 0
    for j in range(n):
        if dist1[i][j] <= l:
            dist2[i][j] = 1

ws(dist2)

q = inn()
for i in range(q):
    s,t = inm()
    d = dist2[s-1][t-1]
    print(d-1 if d<BIG else -1)