珅泽教育的刘老师正在准备一项寻路实践，他请小珅完成下面的任务。

给定一张 $N$ 个顶点、$M$ 条边的简单无向图。随后有 $Q$ 次询问，每次给出顶点 $x$ 和整数 $k$。

对每次询问，请求出所有与 $x$ 的最短距离不超过 $k$ 的顶点编号之和。顶点 $x$ 自身距离为零，也要计入。

输入格式

第一行输入 $N,M$，接下来 M 行输入边。

再输入 Q，随后 Q 行输入 x,k。

输出格式

每次询问输出一行编号之和。

10 9
1 2
2 3
3 4
1 5
2 6
1 7
7 8
6 9
6 10
3
3 0
1 1
8 2

3
15
16

15 14
1 2
1 3
3 4
3 5
1 6
6 7
1 8
2 9
4 10
3 11
8 12
2 13
10 14
14 15
4
12 0
8 1
6 2
9 3

12
21
27
42

20 19
1 2
2 3
1 4
4 5
1 6
1 7
1 8
6 9
2 10
1 11
3 12
11 13
1 14
11 15
8 16
15 17
7 18
18 19
19 20
5
7 0
7 1
2 2
4 3
6 0

7
26
78
142
6

数据范围与约定

• $1 \le N \le 1.5\times10^5$
• $0 \le k \le 3$
• 图为简单无向图