Background

I kept the...
agreement... an agreement.

【You are working very hard.】
I am working very, very hard...

【Even though you said that yesterday too...】
【Welcome back, Chtholly.】

I'm back...
I finally said it out loud...
【Yes, I finally heard it.】
Will red hair look strange?
【It is a very pretty color, it suits you well.】
Really...
I... I'm fine now.
【Really? Is your condition okay?】
【If you are forcing yourself, I won't let you off.】
It's fine. Cooking, laundry... there is still a lot of work to do.
【Don't push yourself too hard.】

Hmph, just be mentally prepared and wait.

Problem 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