Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush


def dijkstra(links, n, l):
    dists = []

    F9 = (1 << 9) - 1
    F30 = (1 << 30) - 1
    INF = 10 ** 18

    for s in range(n):

        q = [s]
        fixed = [-1] * n
        upper = [INF] * n

        while q:
            item = heappop(q)

            v = item & F9
            if fixed[v] != -1:
                continue

            count = item >> 39
            used = (item >> 9) & F30
            fixed[v] = count

            for u, c in links[v]:
                if l - used < c:
                    new_item = ((count + 1) << 39) | (c << 9) | u
                else:
                    new_item = (count << 39) | ((used + c) << 9) | u
                if new_item >= upper[u]:
                    continue
                upper[u] = new_item
                heappush(q, new_item)

        dists.append(fixed)

    return dists


n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()

links = [set() for _ in range(n)]

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if l < c:
        continue
    links[a].add((b, c))
    links[b].add((a, c))

dists = dijkstra(links, n, l)
buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    buf.append(dists[s - 1][t - 1])

print('\n'.join(map(str, buf)))


Fixed submission:
import sys

n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()
INF = 10 ** 18

dists = [[INF] * n for _ in range(n)]

for i in range(n):
    dists[i][i] = 0

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if c > l:
        continue
    dists[a][b] = c
    dists[b][a] = c

for k in range(n):
    dk = dists[k]
    for i in range(n):
        di = dists[i]
        for j in range(n):
            new_dist = di[k] + dk[j]
            if new_dist > l:
                continue
            if di[j] > new_dist:
                di[j] = new_dist

refuels = [[1 if dist < INF else INF for dist in row] for row in dists]

for k in range(n):
    rk = refuels[k]
    for i in range(n):
        ri = refuels[i]
        for j in range(n):
            new_dist = ri[k] + rk[j]
            if ri[j] > new_dist:
                ri[j] = new_dist

buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    refuel = refuels[s - 1][t - 1]
    buf.append(-1 if refuel == INF else refuel - 1)

print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def united_count(self, x):
        return -self.table[self._root(x)]


def dijkstra(links, l, uft):
    dists = []

    F9 = (1 << 9) - 1
    F30 = (1 << 30) - 1
    INF = 10 ** 18

    for s in range(n):

        q = [s]
        fixed = [-1] * n
        upper = [INF] * n
        fixed_count = 0
        limit = uft.united_count(s)

        while q:
            item = heappop(q)

            v = item & F9
            if fixed[v] != -1:
                continue

            count = item >> 39
            used = (item >> 9) & F30
            fixed[v] = count

            fixed_count += 1
            if fixed_count >= limit:
                break

            for u, c in links[v]:
                if l - used < c:
                    new_item = ((count + 1) << 39) | (c << 9) | u
                else:
                    new_item = (count << 39) | ((used + c) << 9) | u
                if new_item >= upper[u]:
                    continue
                upper[u] = new_item
                heappush(q, new_item)

        dists.append(fixed)

    return dists


n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()

links = [set() for _ in range(n)]
uft = UnionFind(n)

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if l < c:
        continue
    links[a].add((b, c))
    links[b].add((a, c))
    uft.union(a, b)

dists = dijkstra(links, l, uft)
buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    buf.append(dists[s - 1][t - 1])

print('\n'.join(map(str, buf)))


Fixed submission:
import sys

n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()
INF = 10 ** 18

dists = [[INF] * n for _ in range(n)]

for i in range(n):
    dists[i][i] = 0

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if c > l:
        continue
    dists[a][b] = c
    dists[b][a] = c

for k in range(n):
    dk = dists[k]
    for i in range(n):
        di = dists[i]
        for j in range(n):
            new_dist = di[k] + dk[j]
            if new_dist > l:
                continue
            if di[j] > new_dist:
                di[j] = new_dist

refuels = [[1 if dist < INF else INF for dist in row] for row in dists]

for k in range(n):
    rk = refuels[k]
    for i in range(n):
        ri = refuels[i]
        for j in range(n):
            new_dist = ri[k] + rk[j]
            if ri[j] > new_dist:
                ri[j] = new_dist

buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    refuel = refuels[s - 1][t - 1]
    buf.append(-1 if refuel == INF else refuel - 1)

print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush


def dijkstra(links, l):
    dists = []

    F9 = (1 << 9) - 1
    F30 = (1 << 30) - 1
    INF = 10 ** 18

    for s in range(n):

        q = [s]
        fixed = [-1] * n
        upper = [INF] * n
        while q:
            item = heappop(q)

            v = item & F9
            if fixed[v] != -1:
                continue

            count = item >> 39
            used = (item >> 9) & F30
            fixed[v] = count

            for u, c in links[v]:
                if l - used < c:
                    new_item = ((count + 1) << 39) | (c << 9) | u
                else:
                    new_item = (count << 39) | ((used + c) << 9) | u
                if new_item >= upper[u]:
                    continue
                heappush(q, new_item)

        dists.append(fixed)

    return dists


n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()

links = [set() for _ in range(n)]

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if l < c:
        continue
    links[a].add((b, c))
    links[b].add((a, c))

dists = dijkstra(links, l)
buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    buf.append(dists[s - 1][t - 1])

print('\n'.join(map(str, buf)))


Fixed submission:
import sys

n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()
INF = 10 ** 18

dists = [[INF] * n for _ in range(n)]

for i in range(n):
    dists[i][i] = 0

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if c > l:
        continue
    dists[a][b] = c
    dists[b][a] = c

for k in range(n):
    dk = dists[k]
    for i in range(n):
        di = dists[i]
        for j in range(n):
            new_dist = di[k] + dk[j]
            if new_dist > l:
                continue
            if di[j] > new_dist:
                di[j] = new_dist

refuels = [[1 if dist < INF else INF for dist in row] for row in dists]

for k in range(n):
    rk = refuels[k]
    for i in range(n):
        ri = refuels[i]
        for j in range(n):
            new_dist = ri[k] + rk[j]
            if ri[j] > new_dist:
                ri[j] = new_dist

buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    refuel = refuels[s - 1][t - 1]
    buf.append(-1 if refuel == INF else refuel - 1)

print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def united_count(self, x):
        return -self.table[self._root(x)]


def dijkstra(s, links, f9, f30):
    q = [s]
    ret = [-1] * n
    visited = set()
    limit = uft.united_count(s)
    while q:
        item = heappop(q)

        v = item & f9
        if v in visited:
            continue
        visited.add(v)

        count = item >> 39
        used = (item >> 9) & f30
        ret[v] = count

        if len(visited) >= limit:
            break

        for u, c in links[v]:
            if u in visited:
                continue
            if l - used < c:
                new_item = ((count + 1) << 39) + (c << 9) + u
            else:
                new_item = (count << 39) + ((used + c) << 9) + u
            heappush(q, new_item)

    return ret


n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()

links = [set() for _ in range(n)]
uft = UnionFind(n)

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if l < c:
        continue
    links[a].add((b, c))
    links[b].add((a, c))
    uft.union(a, b)

f9 = (1 << 9) - 1
f30 = (1 << 30) - 1

ans = [dijkstra(v, links, f9, f30) for v in range(n)]
buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    buf.append(ans[s - 1][t - 1])

print('\n'.join(map(str, buf)))


Fixed submission:
import sys

n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()
INF = 10 ** 18

dists = [[INF] * n for _ in range(n)]

for i in range(n):
    dists[i][i] = 0

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if c > l:
        continue
    dists[a][b] = c
    dists[b][a] = c

for k in range(n):
    dk = dists[k]
    for i in range(n):
        di = dists[i]
        for j in range(n):
            new_dist = di[k] + dk[j]
            if new_dist > l:
                continue
            if di[j] > new_dist:
                di[j] = new_dist

refuels = [[1 if dist < INF else INF for dist in row] for row in dists]

for k in range(n):
    rk = refuels[k]
    for i in range(n):
        ri = refuels[i]
        for j in range(n):
            new_dist = ri[k] + rk[j]
            if ri[j] > new_dist:
                ri[j] = new_dist

buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    refuel = refuels[s - 1][t - 1]
    buf.append(-1 if refuel == INF else refuel - 1)

print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush


def dijkstra(s, links, f9, f30):
    q = [s]
    ret = [-1] * n
    visited = set()
    while q:
        item = heappop(q)

        v = item & f9
        if v in visited:
            continue
        visited.add(v)

        count = item >> 39
        used = (item >> 9) & f30
        ret[v] = count

        for u, c in links[v]:
            if u in visited:
                continue
            if l - used < c:
                new_item = ((count + 1) << 39) + (c << 9) + u
            else:
                new_item = (count << 39) + ((used + c) << 9) + u
            heappush(q, new_item)

    return ret


n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()

links = [set() for _ in range(n)]

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if l < c:
        continue
    links[a].add((b, c))
    links[b].add((a, c))

f9 = (1 << 9) - 1
f30 = (1 << 30) - 1

ans = [dijkstra(v, links, f9, f30) for v in range(n)]
buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    buf.append(ans[s - 1][t - 1])

print('\n'.join(map(str, buf)))


Fixed submission:
import sys

n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()
INF = 10 ** 18

dists = [[INF] * n for _ in range(n)]

for i in range(n):
    dists[i][i] = 0

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if c > l:
        continue
    dists[a][b] = c
    dists[b][a] = c

for k in range(n):
    dk = dists[k]
    for i in range(n):
        di = dists[i]
        for j in range(n):
            new_dist = di[k] + dk[j]
            if new_dist > l:
                continue
            if di[j] > new_dist:
                di[j] = new_dist

refuels = [[1 if dist < INF else INF for dist in row] for row in dists]

for k in range(n):
    rk = refuels[k]
    for i in range(n):
        ri = refuels[i]
        for j in range(n):
            new_dist = ri[k] + rk[j]
            if ri[j] > new_dist:
                ri[j] = new_dist

buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    refuel = refuels[s - 1][t - 1]
    buf.append(-1 if refuel == INF else refuel - 1)

print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush


def dijkstra(s, links, f9, f30):
    q = [s]
    ret = [-1] * n
    visited = set()
    while q:
        item = heappop(q)

        v = item & f9
        if v in visited:
            continue
        visited.add(v)

        count = item >> 39
        used = (item >> 9) & f30
        ret[v] = count

        for u, c in links[v]:
            if u in visited:
                continue
            if l - used < c:
                new_item = ((count + 1) << 39) + (c << 9) + u
            else:
                new_item = (count << 39) + ((used + c) << 9) + u
            heappush(q, new_item)

    return ret


n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()

links = [set() for _ in range(n)]

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if l < c:
        continue
    links[a].add((b, c))
    links[b].add((a, c))

f9 = (1 << 9) - 1
f30 = (1 << 30) - 1

ans = [dijkstra(v, links, f9, f30) for v in range(n)]
buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    buf.append(ans[s - 1][t - 1])

print('\n'.join(map(str, buf)))


Fixed submission:
import sys

n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()
INF = 10 ** 18

dists = [[INF] * n for _ in range(n)]

for i in range(n):
    dists[i][i] = 0

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if c > l:
        continue
    dists[a][b] = c
    dists[b][a] = c

for k in range(n):
    dk = dists[k]
    for i in range(n):
        di = dists[i]
        for j in range(n):
            new_dist = di[k] + dk[j]
            if new_dist > l:
                continue
            if di[j] > new_dist:
                di[j] = new_dist

refuels = [[1 if dist < INF else INF for dist in row] for row in dists]

for k in range(n):
    rk = refuels[k]
    for i in range(n):
        ri = refuels[i]
        for j in range(n):
            new_dist = ri[k] + rk[j]
            if ri[j] > new_dist:
                ri[j] = new_dist

buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    refuel = refuels[s - 1][t - 1]
    buf.append(-1 if refuel == INF else refuel - 1)

print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush


def dijkstra(s, links, f9, f30):
    q = [s]
    ret = [-1] * n
    visited = set()
    while q:
        item = heappop(q)

        v = item & f9
        if v in visited:
            continue
        visited.add(v)

        count = item >> 39
        used = (item >> 9) & f30
        ret[v] = count

        for u, c in links[v]:
            if l - used < c:
                new_item = ((count + 1) << 39) + (c << 9) + u
            else:
                new_item = (count << 39) + ((used + c) << 9) + u
            heappush(q, new_item)

    return ret


n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()

links = [set() for _ in range(n)]

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if l < c:
        continue
    links[a].add((b, c))
    links[b].add((a, c))

f9 = (1 << 9) - 1
f30 = (1 << 30) - 1

ans = [dijkstra(v, links, f9, f30) for v in range(n)]
buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    buf.append(ans[s - 1][t - 1])

print('\n'.join(map(str, buf)))


Fixed submission:
import sys

n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()
INF = 10 ** 18

dists = [[INF] * n for _ in range(n)]

for i in range(n):
    dists[i][i] = 0

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if c > l:
        continue
    dists[a][b] = c
    dists[b][a] = c

for k in range(n):
    dk = dists[k]
    for i in range(n):
        di = dists[i]
        for j in range(n):
            new_dist = di[k] + dk[j]
            if new_dist > l:
                continue
            if di[j] > new_dist:
                di[j] = new_dist

refuels = [[1 if dist < INF else INF for dist in row] for row in dists]

for k in range(n):
    rk = refuels[k]
    for i in range(n):
        ri = refuels[i]
        for j in range(n):
            new_dist = ri[k] + rk[j]
            if ri[j] > new_dist:
                ri[j] = new_dist

buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    refuel = refuels[s - 1][t - 1]
    buf.append(-1 if refuel == INF else refuel - 1)

print('\n'.join(map(str, buf)))