配点 : 500 点
問題文
N 頂点 M 辺の単純無向グラフがあり、各頂点には 1,…,N と番号が付けられています。 i=1,…,M に対し、 i 番目の辺は頂点 ai と頂点 bi を結びます。また、各頂点の次数は 3 以下です。
i=1,…,Q に対し、次のクエリに答えてください。
- 頂点 xi との距離が ki 以下であるような頂点の番号の総和を求めよ。
制約
- 1≤N≤1.5×105
- 0≤M≤min(2N(N−1),23N)
- 1≤ai<bi≤N
- i=j ならば (ai,bi)=(aj,bj)
- 与えられるグラフの各頂点の次数は 3 以下
- 1≤Q≤1.5×105
- 1≤xi≤N
- 0≤ki≤3
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
a1 b1
⋮
aM bM
Q
x1 k1
⋮
xQ kQ
出力
Q 行出力せよ。 i 行目には i 番目のクエリへの答えを出力せよ。
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 が答えです。
2 番目のクエリでは、頂点 2 との距離が 2 以下であるような頂点は頂点 2,3,4,5,6 なのでこれらの総和の 20 が答えになります。
3 番目以降のクエリも同様にして答えを求められます。