小 d 与 k

题目描述

我们有一个由 $N$ 个顶点和 $M$ 条边组成的简单无向图。顶点编号为 $1,\ldots,N$。对每个 $i=1,\ldots,M$，第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。另外，每个顶点的度数至多为 3。

对每个 $i=1,\ldots,Q$，回答下面的查询。

求与顶点 $x_i$ 的距离不超过 $k_i$ 的顶点的编号之和。

输入格式

输入按以下格式从标准输入给出：

N M
a_1 b_1
⋮
a_M b_M
Q
x_1 k_1
⋮
x_Q k_Q

输出格式

输出 $Q$ 行。第 $i$ 行应输出第 $i$ 个查询的答案。

样例

6 5
2 3
3 4
3 5
5 6
2 6
7
1 1
2 2
2 0
2 3
4 1
6 0
4 3

1
20
2
20
7
6
20

对于第 1 个查询，与顶点 1 的距离不超过 1 的顶点只有顶点 1，所以答案是 1。

对于第 2 个查询，与顶点 2 的距离不超过 2 的顶点是顶点 2、3、4、5、6，所以答案是它们的和，即 20。

第 3 个及之后的查询可以类似地回答。

数据范围

• $1 \le N \le 1.5 \times 10^5$
• $0 \le M \le \min(\frac{N(N-1)}{2}, \frac{3N}{2})$
• $1 \le a_i \lt b_i \le N$
• 若 $i\neq j$，则 $(a_i,b_i) \neq (a_j,b_j)$
• 图中每个顶点的度数至多为 3
• $1 \le Q \le 1.5 \times 10^5$
• $1 \le x_i \le N$
• $0 \le k_i \le 3$
• 输入中的所有值均为整数。