CF763E.Timofey and our friends animals

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.

生日派对结束后，季莫费来到了公园里他最喜欢的林荫道。他想在那里喂养他最喜爱的鸟——乌鸦。

众所周知，每棵树上都住着一个乌鸦家庭。林荫道上的树排成一列，编号从 $1$ 到 $n$。某些家庭彼此是朋友。出于某些原因，两个家庭只有在彼此距离不太远时才可能成为朋友，更准确地说：任意一对朋友家庭之间至多间隔 $k-1$ 棵树。形式化地，第 $u$ 棵树上的家庭与第 $v$ 棵树上的家庭可以成为朋友，当且仅当 $|u - v| \leq k$ 成立。

友谊的一个特性是：若某个家庭得知季莫费正在某处喂乌鸦，它便会将该消息通知所有与其为朋友的家庭。因此，当季莫费开始在某棵树下喂乌鸦时，所有与该树上家庭为朋友的家庭、这些家庭的朋友，依此类推，都会飞向喂食地点。当然，该树上的家庭本身也会前往喂食地点。

今天季莫费来到林荫道，发现所有住在编号严格小于 $l$ 或严格大于 $r$ 的树上的家庭均已飞走。因此，无法通过它们传递喂食信息；而且，也无需喂养它们。请帮助季莫费计算：为使所有尚存的家庭均能获知喂食消息，他至少需在多少棵树下进行喂食？题目给出若干种情形（由整数 $l$ 和 $r$ 描述），你需要对每一种情形分别计算答案。

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.

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10^5$，$1 \leq k \leq 5$），其中 $n$ 表示树的数目，$k$ 表示朋友家庭之间可能的最大距离。

第二行包含一个整数 $m$（$0 \leq m \leq n \cdot k$）—— 表示朋友家庭对的数量。

接下来的 $m$ 行中，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq 10^5$），表示位于树 $u$ 和树 $v$ 上的家庭是朋友。保证 $u \neq v$ 且 $|u - v| \leq k$。所有给出的数对互不相同。

下一行包含一个整数 $q$（$1 \leq q \leq 10^5$）—— 表示需要计算答案的情况数量。

接下来的 $q$ 行中，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq 10^5$），表示在该情况下，已飞走的家庭所居住的树编号 $x$ 满足 $x < l$ 或 $x > r$。

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

输出 q 行。第 i 行应包含一个整数——即第 i 种情况下的答案。

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.

在第一个例子中，以下家庭对是朋友关系：(1, 3)、(2, 3) 和 (4, 5)。

• 在第一种情况下，仅剩第一个家庭，因此答案为 1。
• 在第二种情况下，前两个家庭保留下来，且它们彼此不是朋友，因此答案为 2。
• 在第三种情况下，家庭 2 和家庭 3 是朋友，因此只需喂养其中任意一个家庭即可，答案为 1。
• 在第四种情况下，我们可以喂养第一个家庭，随后第三个家庭将从第一个家庭处获得信息，第二个家庭再从第三个家庭处获得信息。答案为 1。
• 在第五种情况下，我们可以喂养第一个和第五个家庭，因此答案为 2。