Background

::::info[题目背景已折叠] 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