E - Small d and k https://atcoder.jp/contests/abc254/tasks/abc254_e

abc254_e.py

from collections import deque


def bfs(x, k):
    que = deque([(x, 0)])
    visits = set([x])
    while que:
        cur, dist = que.popleft()
        for nxt in G[cur]:
            if nxt in visits:
                continue
            if dist < k:
                que.append((nxt, dist + 1))
                visits.add(nxt)
    return sum(visits)


N, M = map(int, input().split())
G = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
Q = int(input())
for _ in range(Q):
    x, k = map(int, input().split())
    print(bfs(x, k))