Timofey and our friends animals
Contest: Codeforces Round 395 (Div. 1)
Difficulty rating: 2900
Tags: data structures, divide and conquer, dsu

After his birthday party, Timofey went to his favorite tree alley in a park. He wants to feed there his favorite birds — crows.

It's widely known that each tree is occupied by a single crow family. The trees in the alley form a row and are numbered from 1 to n. Some families are friends to each other. For some reasons, two families can be friends only if they live not too far from each other, more precisely, there is no more than k - 1 trees between any pair of friend families. Formally, the family on the u-th tree and the family on the v-th tree can be friends only if |u - v| ≤ k holds.

One of the friendship features is that if some family learns that Timofey is feeding crows somewhere, it notifies about this all friend families. Thus, after Timofey starts to feed crows under some tree, all the families that are friends to the family living on this tree, as well as their friends and so on, fly to the feeding place. Of course, the family living on the tree also comes to the feeding place.

Today Timofey came to the alley and noticed that all the families that live on trees with numbers strictly less than l or strictly greater than r have flown away. Thus, it is not possible to pass the information about feeding through them. Moreover, there is no need to feed them. Help Timofey to learn what is the minimum number of trees under which he has to feed crows so that all the families that have remained will get the information about feeding. You are given several situations, described by integers l and r, you need to calculate the answer for all of them.

Input format:
The first line contains integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ 5), where n is the number of trees, and k is the maximum possible distance between friend families.

The next line contains single integer m (0 ≤ m ≤ n·k) — the number of pair of friend families.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ 105), that means that the families on trees u and v are friends. It is guaranteed that u ≠ v and |u - v| ≤ k. All the given pairs are distinct.

The next line contains single integer q (1 ≤ q ≤ 105) — the number of situations you need to calculate the answer in.

Each of the next q lines contains two integers l and r (1 ≤ l ≤ r ≤ 105), that means that in this situation families that have flown away lived on such trees x, so that either x < l or x > r.

Output format:
Print q lines. Line i should contain single integer — the answer in the i-th situation.

Constraints:
Time limit: 7.0 s
Memory limit: 256.0 MB

Note:
In the first example the following family pairs are friends: (1, 3), (2, 3) and (4, 5).

- In the first situation only the first family has remained, so the answer is 1.
- In the second situation the first two families have remained, and they aren't friends, so the answer is 2.
- In the third situation the families 2 and 3 are friends, so it is enough to feed any of them, the answer is 1.
- In the fourth situation we can feed the first family, then the third family will get the information from the first family, and the second family will get the information from the third. The answer is 1.
- In the fifth situation we can feed the first and the fifth families, so the answer is 2.

Example input:
5 3
3
1 3
2 3
4 5
5
1 1
1 2
2 3
1 3
1 5

Example output:
1
2
1
1
2

Editorial:
Let's build a segment tree on crow families. Let's save DSU in each vertex, having information about number of components of connectivity on it. In one vertex will be DSU with size n. In two vertices will be DSU with size n / 2. In four vertices will be DSU with size n / 4. It's easy to show that we will store only O(nlogn) values. Let's understand how we can unite segments. Knowing answer (number of components) for [a; b) and [b; c) we can obtain answer for [a; c) in the following way: We can sum answers for for [a; b) and [b; c) and substract number of components, which united during the "gluing". If components become united, there is edge between vertex in one and vertex in another. We have constraint on edge legth: vertex u and vertex v can be connected only if abs(u - v) ≤ k Then we can easily unite two segments of the segment tree in O(k2) time: we just unite some of the k components of families represented in the end of each segment when they are connected by edge. Segment tree can split query in $${\mathcal {O}}(\log n)$$ already calculated segments. So we can answer the query in $${\mathcal O}(k^{2}\log n)$$ time. Precalc will take nearly $$O(n \log n)$$.
Author's solution: http://pastebin.com/1CwUVyME
Bonus: Solve the problem in $${ \mathcal { O } } ( n k \log n )$$ time for the precalculation and $${\mathcal O}(k^{2}+\log n)$$ time for the query.