题目描述

在遥远的未来，人类已经探索了无数的星球，构建了一个庞大的宇宙网络。这个网络由 $N$ 个星球和 $M$ 条双向的超空间传送通道组成。每个星球都有一个独特的编号，从 $1$ 到 $N$。由于宇宙的神秘力量，每个星球最多只能有 $3$ 条传送通道连接到其他星球。

宇宙信号收集器是一种高科技设备，它可以收集一定范围内的星球信号。信号收集器的范围由它的强度 $k$ 决定，它可以收集距离它所在星球 $x$ 最远为 $k$ 的所有星球的信号。距离定义为两个星球之间需要经过的最少传送通道数。

现在，你作为宇宙信号收集器的中央控制系统，需要处理 $Q$ 个任务。每个任务都会指定一个星球 $x$ 和一个信号收集强度 $k$。你的任务是计算出在信号收集器的范围内（距离不超过 $k$）所有星球的编号之和。这个编号之和对于分析宇宙的结构和资源分布至关重要。

输入描述

• 第一行包含两个整数 $N$ 和 $M$，表示星球的数量和传送通道的数量。
• 接下来 $M$ 行，每行包含两个整数 $a$ 和 $b$，表示星球 $a$ 和星球 $b$ 之间有一条传送通道。
• 接下来一行包含一个整数 $Q$，表示任务的数量。
• 接下来 $Q$ 行，每行包含两个整数 $x$ 和 $k$，表示一个任务，要求计算从星球 $x$ 出发，距离不超过 $k$ 的所有星球编号之和。

输出描述

对于每个任务，输出一行，包含该任务的计算结果。

样例

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，它们的编号之和为 $2 + 3 + 4 + 5 + 6 = 20$。

数据范围

$1 \leq N \leq 1.5 \times 10^5$

$0 \leq M \leq \min\left(\frac{N(N-1)}{2}, \frac{3N}{2}\right)$

$1 \leq a_i < b_i \leq N$

$\text{所有传送通道都是唯一的。}$

$\text{每个星球的传送通道数量不超过 }3\text{。}$

$1 \leq Q \leq 1.5 \times 10^5$

$1 \leq x_i \leq N$

$0 \leq k_i \leq 3$