题目描述

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

对于每个$i=1,\\ldots,Q$，回答以下查询：

• 找到与顶点$x_i$的距离不超过$k_i$的顶点的索引之和。

约束条件

• $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$
• 输入中的所有值都是整数。

输入

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

$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$。
对于第二个查询，与顶点$2$的距离不超过$2$的顶点是顶点$2, 3, 4, 5$和$6$，所以答案是它们的和$20$。
第三个及后续的查询可以采用类似的方式回答。