Description

Chtholly gives you an undirected graph. In each query, you are given a set of pairs $(x_i, y_i)$.

Find how many vertices $u$ in the graph satisfy, for at least one pair $(x_i, y_i)$ in this query, $\mathrm{dist}(u, x_i) \leq y_i$, where $\mathrm{dist}$ denotes the distance between the two vertices in the graph.

If two vertices are disconnected, then $\mathrm{dist} = +\infty$.

Input Format

The first line contains three integers $n, m, q$.

$n$ is the number of vertices, and $m$ is the number of edges.

Then follow $m$ lines, each containing two integers $x, y$, indicating that there is an edge between these two vertices. All edge weights are $1$.

Then there are $q$ queries. For each query, you are first given an integer $a$.

Then follow $a$ lines, each containing two integers $x, y$, representing a pair.

Output Format

Output $q$ lines. Each line contains one integer, the answer to the corresponding query.

5 6 6
2 3
1 3
2 5
1 3
3 2
2 5
1
3 1
1
1 1
1
1 4
1	
5 2
1
1 4
2
1 0
5 1

3
2
4
3
4
3

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477.

Constraints: $1 \leq n \leq 1000$, $1 \leq m, q \leq 10^5$, $\sum a \leq 2.1 \times 10^6$.

Translated by ChatGPT 5