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.

1
9 10
1 2
1 3
2 4
2 5
4 5
3 6
3 7
6 9
8 9
8 7
4
1 2
3 5
6 9
6 7

Case #1:
1
2
1
2

2013 Multi-University Training Contest 8