CF812D.Sagheer and Kindergarten

Sagheer is working at a kindergarten. There are n children and m different toys. These children use well-defined protocols for playing with the toys:

• Each child has a lovely set of toys that he loves to play with. He requests the toys one after another at distinct moments of time. A child starts playing if and only if he is granted all the toys in his lovely set.
• If a child starts playing, then sooner or later he gives the toys back. No child keeps the toys forever.
• Children request toys at distinct moments of time. No two children request a toy at the same time.
• If a child is granted a toy, he never gives it back until he finishes playing with his lovely set.
• If a child is not granted a toy, he waits until he is granted this toy. He can't request another toy while waiting.
• If two children are waiting for the same toy, then the child who requested it first will take the toy first.

Children don't like to play with each other. That's why they never share toys. When a child requests a toy, then granting the toy to this child depends on whether the toy is free or not. If the toy is free, Sagheer will give it to the child. Otherwise, the child has to wait for it and can't request another toy.

Children are smart and can detect if they have to wait forever before they get the toys they want. In such case they start crying. In other words, a crying set is a set of children in which each child is waiting for a toy that is kept by another child in the set.

Now, we have reached a scenario where all the children made all the requests for their lovely sets, except for one child x that still has one last request for his lovely set. Some children are playing while others are waiting for a toy, but no child is crying, and no one has yet finished playing. If the child x is currently waiting for some toy, he makes his last request just after getting that toy. Otherwise, he makes the request right away. When child x will make his last request, how many children will start crying?

You will be given the scenario and q independent queries. Each query will be of the form x y meaning that the last request of the child x is for the toy y. Your task is to help Sagheer find the size of the maximal crying set when child x makes his last request.

萨赫尔在一家幼儿园工作。共有 $n$ 个孩子和 $m$ 种不同的玩具。这些孩子遵循一套明确定义的玩具使用协议：

• 每个孩子都有一组他喜爱的玩具，他按特定的时间顺序依次请求这些玩具。一个孩子当且仅当他被授予其喜爱集合中的所有玩具时，才开始玩耍。
• 如果一个孩子开始玩耍，则他迟早会归还所有玩具。没有任何孩子会永远持有玩具。
• 孩子们在互不相同的时间点请求玩具。不存在两个孩子在同一时刻请求某个玩具的情况。
• 如果一个孩子被授予某个玩具，则他绝不会在完成其喜爱集合中全部玩具的玩耍之前归还该玩具。
• 如果一个孩子未被授予某个他所请求的玩具，他将一直等待，直到获得该玩具；在等待期间，他不能请求其他玩具。
• 若有两个或多个孩子正在等待同一个玩具，则最先提出请求的那个孩子将优先获得该玩具。

孩子们不喜欢一起玩耍，因此他们从不共享玩具。当一个孩子请求某个玩具时，是否将该玩具授予他，取决于该玩具当前是否空闲：若该玩具空闲，萨赫尔便会立即将其交给该孩子；否则，该孩子必须等待，并且在此期间无法请求其他玩具。

孩子们很聪明，能够判断自己是否将永远等待下去而无法获得所需玩具。在这种情况下，他们会开始哭泣。换言之，一个“哭泣集合”（crying set）是指这样一组孩子：其中每个孩子都在等待某个玩具，而该玩具正被该集合中的另一个孩子持有。

目前，我们处于这样一个场景：所有孩子均已提出其喜爱集合中除一人（记为孩子 $x$）之外的所有玩具请求；孩子 $x$ 还剩最后一次请求尚未提出。此时，部分孩子正在玩耍，其余孩子正在等待某个玩具；但尚无任何孩子哭泣，也无人已完成玩耍。如果孩子 $x$ 当前正在等待某个玩具，则他在刚获得该玩具后立即提出最后一次请求；否则，他将立刻提出该请求。那么，当孩子 $x$ 提出其最后一次请求时，将有多少孩子开始哭泣？

你将收到该场景描述以及 $q$ 个相互独立的查询。每个查询形如 $x\ y$，表示孩子 $x$ 的最后一次请求是针对玩具 $y$。你的任务是帮助萨赫尔计算：当孩子 $x$ 提出其最后一次请求时，最大可能的哭泣集合的大小。

The first line contains four integers n, m, k, q (1 ≤ n, m, k, q ≤ 105) — the number of children, toys, scenario requests and queries.

Each of the next k lines contains two integers a, b (1 ≤ a ≤ n and 1 ≤ b ≤ m) — a scenario request meaning child a requests toy b. The requests are given in the order they are made by children.

Each of the next q lines contains two integers x, y (1 ≤ x ≤ n and 1 ≤ y ≤ m) — the request to be added to the scenario meaning child x will request toy y just after getting the toy he is waiting for (if any).

It is guaranteed that the scenario requests are consistent and no child is initially crying. All the scenario requests are distinct and no query coincides with a scenario request.

第一行包含四个整数 $n$、$m$、$k$、$q$（$1 \le n, m, k, q \le 10^5$）——分别表示儿童数量、玩具数量、场景请求数量以及查询数量。

接下来的 $k$ 行中，每行包含两个整数 $a$、$b$（$1 \le a \le n$ 且 $1 \le b \le m$）——表示一个场景请求，含义为儿童 $a$ 请求玩具 $b$。这些请求按儿童发出的顺序给出。

接下来的 $q$ 行中，每行包含两个整数 $x$、$y$（$1 \le x \le n$ 且 $1 \le y \le m$）——表示一个待加入场景的请求，含义为儿童 $x$ 将在获得其正在等待的玩具（如果有的话）后，立即请求玩具 $y$。

保证所有场景请求是一致的，且初始时没有儿童在哭泣。所有场景请求互不相同，且任意查询均不与已有场景请求重合。

For each query, print on a single line the number of children who will start crying when child x makes his last request for toy y. Please answer all queries independent of each other.

对于每个查询，请在单独一行输出：当孩子 x 第二次请求玩具 y 时，将会开始哭泣的孩子人数。请注意，各个查询之间相互独立。

In the first example, child 1 is waiting for toy 2, which child 2 has, while child 2 is waiting for top 3, which child 3 has. When child 3 makes his last request, the toy he requests is held by child 1. Each of the three children is waiting for a toy held by another child and no one is playing, so all the three will start crying.

In the second example, at the beginning, child i is holding toy i for 1 ≤ i ≤ 4. Children 1 and 3 have completed their lovely sets. After they finish playing, toy 3 will be free while toy 1 will be taken by child 2 who has just completed his lovely set. After he finishes, toys 1 and 2 will be free and child 5 will take toy 1. Now:

• In the first query, child 5 will take toy 3 and after he finishes playing, child 4 can play.
• In the second query, child 5 will request toy 4 which is held by child 4. At the same time, child 4 is waiting for toy 1 which is now held by child 5. None of them can play and they will start crying.

在第一个例子中，儿童 1 正在等待玩具 2，而玩具 2 由儿童 2 持有；儿童 2 正在等待玩具 3，而玩具 3 由儿童 3 持有。当儿童 3 提出最后一个请求时，他所请求的玩具正由儿童 1 持有。这三位儿童均在等待被其他儿童持有的玩具，且无人正在玩耍，因此三人都将开始哭泣。

在第二个例子中，初始时，对 $1 \le i \le 4$，儿童 $i$ 持有玩具 $i$。儿童 1 和儿童 3 已完成其喜爱的玩具集合。他们结束玩耍后，玩具 3 将被释放，而玩具 1 将被刚刚完成其喜爱玩具集合的儿童 2 取走。待儿童 2 结束玩耍后，玩具 1 和玩具 2 将被释放，儿童 5 将取走玩具 1。此时：

• 在第一个查询中，儿童 5 将取走玩具 3；待其结束玩耍后，儿童 4 即可开始玩耍。
• 在第二个查询中，儿童 5 将请求由儿童 4 持有的玩具 4；与此同时，儿童 4 正在等待当前由儿童 5 持有的玩具 1。两人均无法开始玩耍，因此都将开始哭泣。