题目描述

强哥所在的社区有 $N$ 户人家，编号为 $1, 2, \ldots, N$。社区中有 $M$ 条小路连接这些人家，每条小路都是双向的。对于 $i = 1, \ldots, M$，第 $i$ 条小路连接人家 $a_i$ 和 $b_i$。 这个社区有一个特点：每户人家最多只和 $3$ 户其他人家直接相连（即每户的“邻居数”不超过 $3$）。

为了促进邻里关系，强哥计划进行 $Q$ 次友好度调查。对于第 $i$ 次调查：

• 强哥想知道：从人家 $x_i$ 出发，沿着小路走不超过 $k_i$ 步能到达的所有人家（包括 $x_i$ 本身）的编号之和是多少？

输入格式

输入格式如下：

$N$ $M$
$a_1$ $b_1$
$\vdots$
$a_M$ $b_M$
$Q$
$x_1$ $k_1$
$\vdots$
$x_Q$ $k_Q$

输出格式

输出 $Q$ 行，每行一个整数，表示对应调查的结果。

输入输出样例

样例 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
20
2
20
7
6
20

说明

• 第 1 次调查：从人家 1 出发，走不超过 1 步能到达的只有人家 1，编号和为 1。
• 第 2 次调查：从人家 2 出发，走不超过 2 步能到达人家 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$
• 若 $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$
• 所有输入均为整数