E - Small d and k Editorial /

Time Limit: 3.5 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

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
  • 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
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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 のみなので 1 が答えです。
2 番目のクエリでは、頂点 2 との距離が 2 以下であるような頂点は頂点 2,3,4,5,6 なのでこれらの総和の 20 が答えになります。
3 番目以降のクエリも同様にして答えを求められます。

Score : 500 points

Problem Statement

We have a simple undirected graph with N vertices and M edges. The vertices are numbered 1,\ldots,N. For each i=1,\ldots,M, the i-th edge connects Vertex a_i and Vertex b_i. Additionally, the degree of each vertex is at most 3.

For each i=1,\ldots,Q, answer the following query.

  • Find the sum of indices of vertices whose distances from Vertex x_i are at most k_i.

Constraints

  • 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), if i\neq j.
  • The degree of each vertex in the graph is at most 3.
  • 1 \leq Q \leq 1.5 \times 10^5
  • 1 \leq x_i \leq N
  • 0 \leq k_i \leq 3
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 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

Sample Output 1

1
20
2
20
7
6
20

For the 1-st query, the only vertex whose distance from Vertex 1 is at most 1 is Vertex 1, so the answer is 1.
For the 2-nd query, the vertices whose distances from Vertex 2 are at most 2 are Vertex 2, 3, 4, 5, and 6, so the answer is their sum, 20.
The 3-rd and subsequent queries can be answered similarly.