← 返回题目列表

Codeforces · 763/E

E. 蒂莫菲和我们的动物朋友

中文机器翻译题面 查看原题

生日聚会结束后,蒂莫菲去了他最喜欢的公园树巷。他想在那里喂他最喜欢的鸟——乌鸦。

众所周知,每棵树都由一个乌鸦家族占据。巷子里的树排成一排,编号为1到n。有些家庭彼此是朋友。由于某些原因,两个家庭只有在住得距离不太远的情况下才能成为朋友,更准确地说,任何一对朋友家庭之间不超过 k-1 棵树。形式上,只有满足 |u - v| 时,第 u 棵树上的家庭和第 v 棵树上的家庭才能成为朋友。 ≤ k 成立。

友谊功能之一是,如果某个家庭得知蒂莫菲在某处喂乌鸦,它会通知所有朋友家庭。因此,当蒂莫菲开始在某棵树下喂乌鸦后,所有住在这棵树上的家庭的朋友,以及他们的朋友等等,都会飞到喂食的地方。当然,住在树上的一家人也会来到觅食的地方。

今天蒂莫菲来到巷子里,发现所有住在树上的、数量严格小于l或严格大于r的家庭都飞走了。因此,不可能通过它们传递有关喂养的信息。而且,不需要喂它们。帮助蒂莫菲了解他必须在多少棵树下喂乌鸦,以便剩下的所有家庭都能获得有关喂食的信息。给你几种情况,用整数 l 和 r 描述,你需要计算所有情况的答案。

输入

第一行包含整数 n 和 k (1 ≤ n ≤ 105, 1 ≤ k ≤ 5),其中 n 是树的数量,k 是朋友家庭之间的最大可能距离。

下一行包含单个整数 m (0 ≤ m ≤ n·k) — 朋友家庭对的数量。

接下来的 m 行中的每一行都包含两个整数 u 和 v (1 ≤ u, v ≤ 105),这意味着树上的家庭 u 和 v 是朋友。保证 u ≠ v 且 |u - v| ≤ k。所有给定的对都是不同的。

下一行包含单个整数 q (1 ≤ q ≤ 105) — 您需要计算答案的情况数。

接下来的 q 行包含两个整数 l 和 r (1 ≤ l ≤ r ≤ 105),这意味着在这种情况下,飞走的家庭生活在这样的树 x 上,因此 x < l 或 x > r。

输出

打印 q 行。第 i 行应包含单个整数——第 i 种情况的答案。

示例

输入 #1

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

输出 #1

1
2
1
1
2

注意

在第一个示例中,以下家庭对是朋友:(1, 3)、(2, 3) 和 (4, 5)。

- 在第一种情况下,只剩下第一个家庭,所以答案是 1。
- 在第二种情况下,前两个家庭仍然存在,而且他们不是朋友,所以答案是 2。
- 在第三种情况中,家庭2和家庭3是朋友,所以喂饱他们中的任何一个就足够了,答案是1。
- 在第四种情况下,我们可以养活第一个家庭,然后第三个家庭将从第一个家庭获得信息,第二个家庭将从第三个家庭获得信息。答案是1。
- 在第五种情况下,我们可以养活第一和第五个家庭,所以答案是2。