Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def WF(mat, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
    return mat


N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    roads[a-1][b-1] = c
    roads[b-1][a-1] = c

roads = WF(roads)
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1
kyuyu = WF(kyuyu)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def WF(mat, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
    return mat


N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    roads[a-1][b-1] = c
    roads[b-1][a-1] = c

roads = WF(roads, N)
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1
kyuyu = WF(kyuyu, N)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    if c <= L:  # 移動出来ない経路は消す
        roads[a-1][b-1] = c
        roads[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            roads[i][j] = min(roads[i][j], roads[i][k]+roads[k][j])

for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            kyuyu[i][j] = min(kyuyu[i][j], kyuyu[i][k]+kyuyu[k][j])

Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def WF(mat, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
    return mat


N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    roads[a-1][b-1] = c
    roads[b-1][a-1] = c

roads = WF(roads, N)
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1
kyuyu = WF(kyuyu, N)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in range(N)]
kyuyu = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    if c <= L:  # 移動出来ない経路は消す
        roads[a-1][b-1] = c
        roads[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            roads[i][j] = min(roads[i][j], roads[i][k]+roads[k][j])

for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            kyuyu[i][j] = min(kyuyu[i][j], kyuyu[i][k]+kyuyu[k][j])

Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def WF(mat, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
    return mat


N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    roads[a-1][b-1] = c
    roads[b-1][a-1] = c

roads = WF(roads, N)
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1
kyuyu = WF(kyuyu, N)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in range(N)]
kyuyu = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    if c <= L:  # 移動出来ない経路は消す
        roads[a-1][b-1] = c
        roads[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            roads[i][j] = min(roads[i][j], roads[i][k]+roads[k][j])

for i in range(N):
    for j in range(N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            kyuyu[i][j] = min(kyuyu[i][j], kyuyu[i][k]+kyuyu[k][j])

Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def WF(mat, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
    return mat


N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    roads[a-1][b-1] = c
    roads[b-1][a-1] = c

roads = WF(roads, N)
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1
kyuyu = WF(kyuyu, N)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in range(N)]
kyuyu = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    if c <= L:  # 移動出来ない経路は消す
        roads[a-1][b-1] = c
        roads[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            roads[i][j] = min(roads[i][j], roads[i][k]+roads[k][j])

for i in range(N):
    for j in range(N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            kyuyu[i][j] = min(kyuyu[i][j], kyuyu[i][k]+kyuyu[k][j])

Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def WF(mat, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
    return mat


N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    roads[a-1][b-1] = c
    roads[b-1][a-1] = c

roads = WF(roads, N)
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1
kyuyu = WF(kyuyu, N)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, L = map(int, input().split())
adj = [set() for _ in range(N)]
roads = [[-1]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    if c <= L:  # 移動出来ない経路は消す
        roads[a-1][b-1] = c
        roads[b-1][a-1] = c
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)


def calc_ans(start, end):
    dist = [[-1]*(N+1) for _ in range(N)]  # dist[i][j] iまで給油j会で行った時の残りの最大値
    dist[start][0] = L
    Q = [[0, start]]  # (給油回数、current node)
    while Q:
        kyuyu, cur_node = heapq.heappop(Q)
        if cur_node == end:
            return kyuyu
        remain = dist[cur_node][kyuyu]
        assert remain != -1
        for next in adj[cur_node]:
            # 給油せずにいく
            to_next = roads[cur_node][next]
            if dist[next][kyuyu] == -1:
                if to_next <= remain:  # 給油なしでいける
                    dist[next][kyuyu] = remain-to_next
                    heapq.heappush(Q, [kyuyu, next])
            else:
                cur_cost = dist[next][kyuyu]
                if to_next-remain > cur_cost:
                    dist[next][kyuyu] = to_next-cur_cost
                    Q.append([kyuyu, next])
                    heapq.heappush(Q, [kyuyu, next])
            #　給油していく
            if kyuyu+1 <= N and dist[next][kyuyu+1] == -1:
                dist[next][kyuyu+1] = L-to_next
                heapq.heappush(Q, [kyuyu+1, next])
            elif kyuyu+1 <= N:
                cur_cost = dist[next][kyuyu+1]
                if L-to_next > cur_cost:
                    dist[next][kyuyu] = L-to_next
                    heapq.heappush(Q, [kyuyu+1, next])

    return -1


Q = int(input())
query = [list(map(lambda x:int(x)-1, input().split())) for _ in range(Q)]

for s, t in query:
    print(calc_ans(s, t))


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def WF(mat, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
    return mat


N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    roads[a-1][b-1] = c
    roads[b-1][a-1] = c

roads = WF(roads, N)
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1
kyuyu = WF(kyuyu, N)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, L = map(int, input().split())
adj = [set() for _ in range(N)]
roads = [[-1]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    if c <= L:  # 移動出来ない経路は消す
        roads[a-1][b-1] = c
        roads[b-1][a-1] = c
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)


def calc_ans(start, end):
    dist = [[-1]*(N+1) for _ in range(N)]  # dist[i][j] iまで給油j会で行った時の残りの最大値
    dist[start][0] = L
    Q = [[0, start]]  # (給油回数、current node)
    while Q:
        kyuyu, cur_node = heapq.heappop(Q)
        if cur_node == end:
            return kyuyu
        remain = dist[cur_node][kyuyu]
        assert remain != -1
        for next in adj[cur_node]:
            # 給油せずにいく
            to_next = roads[cur_node][next]
            if dist[next][kyuyu] == -1:
                if to_next <= remain:  # 給油なしでいける
                    dist[next][kyuyu] = remain-to_next
                    heapq.heappush(Q, [kyuyu, next])
            else:
                cur_cost = dist[next][kyuyu]
                if to_next-remain > cur_cost:
                    dist[next][kyuyu] = to_next-cur_cost
                    Q.append([kyuyu, next])
                    heapq.heappush(Q, [kyuyu, next])
            #　給油していく
            if kyuyu+1 <= N and dist[next][kyuyu+1] == -1:
                dist[next][kyuyu+1] = L-to_next
                heapq.heappush(Q, [kyuyu+1, next])
            elif kyuyu+1 <= N:
                cur_cost = dist[next][kyuyu+1]
                if L-to_next > cur_cost:
                    dist[next][kyuyu] = L-to_next
                    heapq.heappush(Q, [kyuyu+1, next])

    return -1


Q = int(input())
query = [list(map(lambda x:int(x)-1, input().split())) for _ in range(Q)]

for s, t in query:
    print(calc_ans(s, t))


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def WF(mat, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
    return mat


N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    roads[a-1][b-1] = c
    roads[b-1][a-1] = c

roads = WF(roads, N)
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1
kyuyu = WF(kyuyu, N)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, L = map(int, input().split())
adj = [set() for _ in range(N)]
roads = [[-1]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    if c <= L:  # 移動出来ない経路は消す
        roads[a-1][b-1] = c
        roads[b-1][a-1] = c
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)


def calc_ans(start, end):
    dist = [[-1]*(N+1) for _ in range(N)]  # dist[i][j] iまで給油j会で行った時の残りの最大値
    dist[start][0] = L
    Q = [[0, start]]  # (給油回数、current node)
    while Q:
        kyuyu, cur_node = heapq.heappop(Q)
        if cur_node == end:
            return kyuyu
        remain = dist[cur_node][kyuyu]
        assert remain != -1
        for next in adj[cur_node]:
            # 給油せずにいく
            to_next = roads[cur_node][next]
            if dist[next][kyuyu] == -1:
                if to_next <= remain:  # 給油なしでいける
                    dist[next][kyuyu] = remain-to_next
                    heapq.heappush(Q, [kyuyu, next])
            else:
                cur_cost = dist[next][kyuyu]
                if to_next-remain > cur_cost:
                    dist[next][kyuyu] = to_next-cur_cost
                    Q.append([kyuyu, next])
                    heapq.heappush(Q, [kyuyu, next])
            #　給油していく
            if kyuyu+1 <= N and dist[next][kyuyu+1] == -1:
                dist[next][kyuyu+1] = L-to_next
                heapq.heappush(Q, [kyuyu+1, next])
            elif kyuyu+1 <= N:
                cur_cost = dist[next][kyuyu+1]
                if L-to_next > cur_cost:
                    dist[next][kyuyu] = L-to_next
                    heapq.heappush(Q, [kyuyu+1, next])

    for i in range(N):
        if dist[end][i] >= 0:
            return i
    return -1


Q = int(input())
query = [list(map(lambda x:int(x)-1, input().split())) for _ in range(Q)]

for s, t in query:
    print(calc_ans(s, t))


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def WF(mat, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
    return mat


N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    roads[a-1][b-1] = c
    roads[b-1][a-1] = c

roads = WF(roads, N)
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1
kyuyu = WF(kyuyu, N)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, L = map(int, input().split())
adj = [set() for _ in range(N)]
roads = [[-1]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    if c <= L:  # 移動出来ない経路は消す
        roads[a-1][b-1] = c
        roads[b-1][a-1] = c
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)


def calc_ans(start, end):
    dist = [[-1]*(N+1) for _ in range(N)]  # dist[i][j] iまで給油j会で行った時の残りの最大値
    dist[start][0] = L
    Q = [[0, start]]  # (給油回数、current node)
    while Q:
        kyuyu, cur_node = heapq.heappop(Q)
        if cur_node == end:
            continue
        remain = dist[cur_node][kyuyu]
        assert remain != -1
        for next in adj[cur_node]:
            # 給油せずにいく
            to_next = roads[cur_node][next]
            if dist[next][kyuyu] == -1:
                if to_next <= remain:  # 給油なしでいける
                    dist[next][kyuyu] = remain-to_next
                    heapq.heappush(Q, [kyuyu, next])
            else:
                cur_cost = dist[next][kyuyu]
                if to_next-remain > cur_cost:
                    dist[next][kyuyu] = to_next-cur_cost
                    Q.append([kyuyu, next])
                    heapq.heappush(Q, [kyuyu, next])
            #　給油していく
            if kyuyu+1 <= N and dist[next][kyuyu+1] == -1:
                dist[next][kyuyu+1] = L-to_next
                heapq.heappush(Q, [kyuyu+1, next])
            elif kyuyu+1 <= N:
                cur_cost = dist[next][kyuyu+1]
                if L-to_next > cur_cost:
                    dist[next][kyuyu] = L-to_next
                    heapq.heappush(Q, [kyuyu+1, next])

    for i in range(N):
        if dist[end][i] >= 0:
            return i
    return -1


Q = int(input())
query = [list(map(lambda x:int(x)-1, input().split())) for _ in range(Q)]

for s, t in query:
    print(calc_ans(s, t))


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def WF(mat, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
    return mat


N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    roads[a-1][b-1] = c
    roads[b-1][a-1] = c

roads = WF(roads, N)
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1
kyuyu = WF(kyuyu, N)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)