← 返回题目列表

AtCoder · abc254_e

H. 小 d 和 k

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

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

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

  • 求与 Vertex 距离的顶点索引之和 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-st查询,距离Vertex唯一的顶点 1 最多是 1 是顶点 1,所以答案是 1.
对于 2-nd查询,距Vertex距离的顶点 2 最多 2 是顶点 2, 3, 4, 5,和 6,所以答案是它们的总和, 20.
的 3-rd 和后续查询可以类似地回答。