4677：Query on Graph

Given an undirected and connected graph with n vertices and m edges, and q queries on the graph. In each query, you are given two integers l, r, and output the number of connected components of the graph only with vertices labelled from l to r (that means deleting the vertices labelled 1, 2, ..., l-1, r+1, r+2, ... , n and the corresponding edges from the graph, then output the number of connected components).

The first line of the input contains an integer T (T<=10), indicating the number of test cases.
For each test case, the first line contains two integers n, m (1<=n<=30000, n-1<=m<=3*n), as described above.
For next m lines, each line contains two integers u, v (1<=u, v<=n), indicates there is an edge between vertex u and vertex v.
Next line is an integer q(1<=q<=30000), indicates the number of queries.
For next q lines, each line contains two integers l, r (1<=l<=r<=n), indicates the query.
The graph are generated randomly and there are only few big datas.

For each test case, output "Case #X:" first, X is the test number. Then output q lines, each with a number, the answer to each query.