← 返回题目列表

Codeforces · 812/D

D. Sagheer 和幼儿园

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

Sagheer 在幼儿园工作。有 n 个孩子和 m 个不同的玩具。这些孩子使用明确定义的协议来玩玩具:

- 每个孩子都有一套他喜欢玩的可爱玩具。他在不同的时间点一件又一件地索取玩具。当且仅当孩子获得了他可爱的套装中的所有玩具时,他才开始玩耍。
- 如果孩子开始玩耍,那么他迟早会归还玩具。没有哪个孩子会永远保留玩具。
- 孩子们在不同的时间点要求玩具。没有两个孩子会同时要求一个玩具。
- 如果一个孩子得到了一个玩具,他永远不会把它还给他,直到他玩完他可爱的玩具为止。
- 如果孩子没有获得玩具,他会等待直到获得该玩具。在等待期间他不能再要求另一个玩具。
- 如果两个孩子正在等待同一个玩具,那么最先请求的孩子将先拿走玩具。

孩子们不喜欢互相玩耍。这就是为什么他们从不分享玩具。当一个孩子请求一个玩具时,将玩具授予该孩子取决于该玩具是否免费。如果玩具是免费的,萨吉尔会把它送给孩子。否则,孩子必须等待并且无法要求另一个玩具。

孩子们很聪明,能够察觉到他们是否需要永远等待才能得到他们想要的玩具。在这种情况下,他们开始哭泣。换句话说,哭泣组是一组孩子,其中每个孩子都在等待组中另一个孩子保留的玩具。

现在,我们遇到了这样一种情况:所有孩子都提出了对他们可爱套装的所有请求,除了一个孩子 x 仍然对他的可爱套装有最后一个请求。有些孩子正在玩耍,有些则在等待玩具,但没有孩子哭,也没有人玩完。如果孩子 x 当前正在等待某个玩具,他在得到该玩具后立即提出最后一个请求。否则,他会立即提出请求。当孩子 x 提出最后一个要求时,有多少孩子会开始哭泣?

您将获得场景和 q 个独立查询。每个查询的形式为 x y ,这意味着孩子 x 的最后一个请求是针对玩具 y 的。你的任务是帮助 Sagheer 找到当孩子 x 提出最后一个请求时最大哭泣集的大小。

输入

第一行包含四个整数 n、m、k、q (1 ≤ n、m、k、q ≤ 105) — 儿童、玩具、场景请求和查询的数量。

接下来的 k 行中的每一行都包含两个整数 a、b(1 ≤ a ≤ n 和 1 ≤ b ≤ m)——一个场景请求,表示孩子 a 请求玩具 b。这些请求按照儿童提出的顺序提出。

接下来的 q 行中的每一行都包含两个整数 x、y(1 ≤ x ≤ n 和 1 ≤ y ≤ m)——要添加到场景中的请求,意味着孩子 x 在获得他正在等待的玩具(如果有)后将请求玩具 y。

保证场景请求一致并且没有孩子最初哭泣。所有场景请求都是不同的,并且没有查询与场景请求一致。

输出

对于每个查询,在单行上打印当孩子 x 最后一次请求玩具 y 时将开始哭泣的孩子数量。请独立回答所有问题。

示例

输入 #1

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

输出 #1

3

输入 #2

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

输出 #2

0
2

注意

在第一个示例中,孩子 1 正在等待孩子 2 拥有的玩具 2,而孩子 2 正在等待孩子 3 拥有的玩具 3。当孩子 3 提出最后一个请求时,他请求的玩具被孩子 1 拿着。三个孩子中的每一个都在等待另一个孩子拿着的玩具,而没有人玩,所以三个孩子都会开始哭。

在第二个例子中,一开始,孩子 i 拿着玩具 i 1 ≤ i ≤ 4。孩子 1 和 3 已经完成了他们可爱的套装。当他们玩完后,玩具 3 将被释放,而玩具 1 将被刚刚完成他可爱的套装的孩子 2 拿走。当他完成后,玩具 1 和 2 将被释放,孩子 5 将拿走玩具 1。现在:

- 在第一个查询中,孩子 5 将拿走玩具 3,玩完后,孩子 4 可以玩。
- 在第二个查询中,孩子 5 将请求孩子 4 拿着的玩具 4。同时,孩子 4 正在等待现在由孩子 5 拿着的玩具 1。他们都不能玩,他们会开始哭泣。