题目描述

给定 $n$ 个点 $m$ 条边的简单无向图，特别地，保证每个点的度数不超过 $3$。$q$ 次询问，给定 $x, k$，求所有距离 $x$ 不超过 $k$ 的点（包括 $x$）的编号和。

输入格式

第一行输入 $N$ $M$

接下来 $M$ 行每行两个整数 $u_i$ $v_i$

接下来先输入一个 $Q$

接下来 $Q$ 行每行输入两个数字 $x_i$ $k_i$

输出格式

输出一共输出 $q$ 行。

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$ ，因此答案是 $1$ 。 对于第 $2$ 个查询，与顶点 $2$ 的距离最多为 $2$ 的顶点是顶点 $2$ 、 $3$ 、 $4$ 、 $5$ 和 $6$ ，因此答案是它们的总和 $20$ 。

提示

• $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$
• $(a_i,b_i) \neq (a_j,b_j)$ , 如果 $i\neq j$ .
• 图中每个顶点的度最多为 $3$ 。
• $1 \leq Q \leq 1.5 \times 10^5$
• $1 \leq x_i \leq N$
• $0 \leq k_i \leq 3$
• 输入值均为整数。