CF763E Timofey and our friends animals

在庆祝完生日后，Timofey 来到了他最喜欢的公园林荫道。他想在这里喂他最爱的鸟——乌鸦。 众所周知，每棵树上都住着一个乌鸦家庭。林荫道上的树排成一排，编号为 $1$ 到 $n$。有些家庭彼此是朋友。由于某些原因，两个家庭只有在它们之间最多相隔 $k-1$ 棵树时，才能成为朋友。准确来说，住在第 $u$ 棵树的家庭和住在第 $v$ 棵树的家庭只有当 $|u-v| \leq k$ 时，才能成为朋友。 友谊的一个特征是，如果某个家庭发现 Timofey 正在某棵树下喂乌鸦，它会通知所有朋友家庭。如此一来，当 Timofey 在某棵树下喂乌鸦时，这棵树上的家庭、它所有的朋友家庭、朋友的朋友......全都会赶来吃食。当然，自己也会过来。 今天，Timofey 来到林荫道时，他发现编号严格小于 $l$ 或严格大于 $r$ 的树上的乌鸦家庭都已经飞走了。因此，信息无法通过他们传递，也无需喂它们。请你帮 Timofey 计算，至少需要在多少棵树下喂乌鸦，才能让剩下的所有家庭都收到信息。你将会获得多个不同的情况，每种情况通过整数 $l$ 和 $r$ 给出，你需要对每种情况回答这个最小喂食树的数量。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10^{5}$，$1 \leq k \leq 5$），分别表示树的数量和两家成为朋友的最大距离。 第二行包含一个整数 $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$ 的树上的家庭都已飞走。

输出 $q$ 行。第 $i$ 行应为第 $i$ 个情况的答案——至少要在多少棵树下喂乌鸦，才能让所有仍在的家庭都获得消息。

在第一个样例中，好友对有 $(1,3)$、$(2,3)$ 和 $(4,5)$。 - 第一种情况，只剩下第一个家庭，因此答案是 $1$。 - 第二种情况，前两个家庭都留下，但它们不是朋友，所以答案是 $2$。 - 第三种情况，第 $2$ 和第 $3$ 个家庭是朋友，选其中任何一个即可，答案为 $1$。 - 第四种情况，可以只喂第一个家庭，然后第 $3$ 个会从第 $1$ 个得到消息，第 $2$ 个又能从第 $3$ 个得到消息，因此答案为 $1$。 - 第五种情况，喂第 $1$ 和第 $5$ 个家庭即可，答案为 $2$。 由 ChatGPT 5 翻译