问题描述

我们有一个简单的无向图，包含 $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$

$\vdots$

$a_M$ $b_M$

$Q$

$x_1$ $k_1$

$\vdots$

$x_Q$ $k_Q$

输出格式

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

样例输入 1

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

1
20
2
20
7
6
20

对于第 $1$ 个查询，唯一一个与顶点 $1$ 距离至多为 $1$ 的顶点是顶点 $1$，所以答案是 $1$。 对于第 $2$ 个查询，与顶点 $2$ 距离至多为 $2$ 的顶点是顶点 $2$、$3$、$4$、$5$ 和 $6$，所以答案是它们的和，$20$。 第三个及后续查询可以类似回答。

数据规模

$100\%$ 的数据：

• $1 \leq N \leq 1.5 \times 10^5$
• $0 \leq M \leq \min (\frac{N(N-1)}{2},\frac{3N}{2})$
• $1 \leq a_i \lt b_i \leq N$
• 如果 $i\neq j$，则 $(a_i,b_i) \neq (a_j,b_j)$。
• 图中每个顶点的度数最多为 $3$。
• $1 \leq Q \leq 1.5 \times 10^5$
• $1 \leq x_i \leq N$
• $0 \leq k_i \leq 3$

其中约 $40\%$ 的数据，$N, M, Q$ 最大不超过 $1000$。