P6328 I Am a Cactus.

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. 

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$.

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 $q$ lines. Each line contains one integer, the answer to the corresponding query.

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