Graph Query with Distance Constraints

Given an undirected graph, you need to process several queries. In each query, you are given a set of pairs \((x_i, y_i)\). For each query, count the number of vertices \(u\) such that there exists at least one pair \((x_i,y_i)\) satisfying \(\mathrm{dist}(u,x_i) \le y_i\). Here, \(\mathrm{dist}(u,v)\) denotes the shortest path distance between vertices \(u\) and \(v\) in the graph. If two vertices are not connected, the distance is defined as \(+\infty\).

inputFormat

The input begins with two integers \(n\) and \(m\) representing the number of vertices and edges of the graph respectively. The next \(m\) lines each contain two integers \(u\) and \(v\) indicating an undirected edge between vertices \(u\) and \(v\). Then an integer \(q\) is given representing the number of queries. Each query is formatted as follows:

The first line of the query contains an integer \(k\), the number of pairs. Each of the next \(k\) lines contains two integers \(x_i\) and \(y_i\).

outputFormat

For each query, output a single integer representing the number of vertices \(u\) that satisfy the condition.

sample

5 4
1 2
2 3
3 4
4 5
2
2
1 1
3 1
1
2 2

3
5