CF812D Sagheer and Kindergarten

Sagheer 在幼儿园工作。幼儿园里有 $ n $ 个孩子和 $ m $ 种不同的玩具。这些孩子玩玩具时按以下规则进行： - 每个孩子都有一套自己喜欢的玩具，他会依次在不同的时间请求这些玩具。只有当他获得了所有喜欢的玩具后，才开始玩。 - 孩子获得玩具后，迟早会归还，因此没有孩子会永远保留玩具。 - 请求时间错开，孩子们不会同时请求玩具。 - 孩子一旦得到某个玩具，直到他完成玩耍之前，不会归还该玩具。 - 要是有孩子没获得请求的玩具，他将一直等待，不能在此期间请求其他玩具。 - 若两个孩子同时等同一个玩具，先请求的孩子会优先获得。 孩子们不喜欢一起玩，所以他们从不共享玩具。孩子请求玩具时，如果玩具空闲，Sagheer 会把它给这个孩子；否则，孩子只能继续等待并无法请求其他玩具。 聪明的孩子能察觉到如果某个玩具总是拿不到，那他们就会一直等待。若出现某个孩子的请求符合此类情况，他们就会开始哭泣。也就是说，一个"哭泣集合"是指每个孩子都在等另一个孩子持有的玩具的集合。 在当前场景中，所有孩子都已完成对自己喜欢玩具的请求，只有一个孩子 $ x $ 剩下最后一个请求未完成。一些孩子正在玩，而其他孩子在等待，但没有孩子在哭泣，且还没有人完成玩耍。如果孩子 $ x $ 此时在等待某个玩具，他会在获得这个玩具之后立即请求最后一个玩具；如果没有等待，他会立刻请求。你需要确定当孩子 $ x $ 发出他的最后一个请求时，有多少孩子会开始哭泣。 有 $ q $ 个独立的查询，每个查询形如 $ x $ 和 $ y $，表示孩子 $ x $ 的最后请求是玩具 $ y $。你的任务是帮助 Sagheer 找出在孩子 $ x $ 发出最后请求时，最大哭泣集合的大小。

第一行包含四个整数 $ n $，$ m $，$ k $，$ q $（$ 1 \leq n, m, k, q \leq 10^5 $），分别代表孩子数、玩具数、场景中的请求数和查询数。 接下来 $ k $ 行中，每行两个整数 $ a $ 和 $ b $（$ 1 \leq a \leq n $，$ 1 \leq b \leq m $）表示在场景请求中，孩子 $ a $ 请求玩具 $ b $。请求按照孩子们的请求时间顺序给出。 随后 $ q $ 行中，每行两个整数 $ x $ 和 $ y $（$ 1 \leq x \leq n $，$ 1 \leq y \leq m $）表示添加的请求，即孩子 $ x $ 将在获得他所等待的玩具（如果有的话）之后请求玩具 $ y $。 输入确保场景中的请求是一致的，且起初没有孩子在哭泣。所有场景请求都是唯一的，并且查询不会与场景请求重合。

对于每个查询，输出一行，当孩子 $ x $ 进行最后请求玩具 $ y $ 时，会有多少孩子开始哭泣。每对查询独立进行回答。

在第一个例子中，孩子 $ 1 $ 正在等待玩具 $ 2 $，而玩具 $ 2 $ 被孩子 $ 2 $ 拿着；孩子 $ 2 $ 正在等待玩具 $ 3 $，而玩具 $ 3 $ 在孩子 $ 3 $ 手中。当孩子 $ 3 $ 发起最后请求时，所需的玩具在孩子 $ 1 $ 手上。这意味着三个孩子互相等待对方的玩具，因而三人都会开始哭泣。 在第二个例子中，开始时对每个 $ 1 \leq i \leq 4 $，孩子 $ i $ 都持有玩具 $ i $。孩子 $ 1 $ 与孩子 $ 3 $ 已完成他们的玩具集，他们的玩具集完成后玩具 $ 3 $ 空闲，而玩具 $ 1 $ 会被刚完成玩具集的孩子 $ 2 $ 拿走。之后，玩具 $ 1 $ 和 $ 2 $ 都会空闲，孩子 $ 5 $ 会取得玩具 $ 1 $。情况如下： - 在第一个查询中，孩子 $ 5 $ 会拿到玩具 $ 3 $，他完成玩耍后，孩子 $ 4 $ 能开始玩耍。 - 在第二个查询中，孩子 $ 5 $ 请求玩具 $ 4 $，而这时玩具 $ 4 $ 在孩子 $ 4 $ 手中，同时孩子 $ 4 $ 等待玩具 $ 1 $，该玩具此时在孩子 $ 5 $ 手中。两人都不能玩，因此会开始哭泣。 **本翻译由 AI 自动生成**