Connected Components in a Graph Subsequence

You are given an undirected graph \(G(V, E)\), where each edge in \(E\) is represented by a tuple \((u, v)\). The edges are arranged in a fixed sequence \(A\) of length \(|E|\). You are then given \(q\) queries, each containing a pair \((l, r)\). For each query, you need to consider the graph \(G'(V, \cup_{i=l}^{r} \{A_i\})\) which consists of all vertices \(V\) and the subset of edges from the sequence between indices \(l\) and \(r\) (inclusive). Your task is to determine the number of connected components in \(G'\).

Note: The indices \(l\) and \(r\) are 1-indexed. If no edge is selected, the number of connected components is simply \(n\), the number of vertices.

inputFormat

The first line contains two integers \(n\) and \(m\) denoting the number of vertices and edges respectively.

The following \(m\) lines each contain two integers \(u\) and \(v\) representing an undirected edge between vertices \(u\) and \(v\). These edges form the sequence \(A\) in the order they are given.

The next line contains an integer \(q\) representing the number of queries.

Each of the next \(q\) lines contains two integers \(l\) and \(r\), representing a query over the edge sequence from index \(l\) to \(r\) (inclusive).

outputFormat

For each query, output a single integer on a new line indicating the number of connected components in the subgraph defined by the selected edges.

sample

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

3
1
2