English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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.
[samples]
## Note
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.
Sagheer 在一所幼儿园工作。有 #cf_span[n] 个孩子和 #cf_span[m] 种不同的玩具。这些孩子有明确的玩玩具协议：
孩子们不喜欢互相玩。因此他们从不共享玩具。当一个孩子请求一个玩具时，是否将该玩具授予该孩子取决于该玩具是否空闲。如果玩具空闲，Sagheer 会将其交给孩子。否则，孩子必须等待，且不能请求其他玩具。
孩子们很聪明，能判断自己是否将永远等待下去才能得到想要的玩具。在这种情况下，他们会开始哭。换句话说，一个哭泣集合是一组孩子，其中每个孩子都在等待另一个孩子持有的玩具。
现在，我们到达了一个场景：所有孩子都已提出他们想要的玩具集合的所有请求，除了一个孩子 #cf_span[x]，他还有一个最后的请求。有些孩子正在玩，有些孩子在等待玩具，但没有任何孩子在哭，也没有任何人完成玩耍。如果孩子 #cf_span[x] 当前正在等待某个玩具，他将在拿到该玩具后立即提出最后一个请求。否则，他立即提出请求。当孩子 #cf_span[x] 提出他的最后一个请求时，会有多少孩子开始哭？
你将获得该场景和 #cf_span[q] 个独立查询。每个查询的形式为 #cf_span[x] #cf_span[y]，表示孩子 #cf_span[x] 的最后一个请求是针对玩具 #cf_span[y]。你的任务是帮助 Sagheer 找出当孩子 #cf_span[x] 提出最后一个请求时，最大哭泣集合的大小。
第一行包含四个整数 #cf_span[n], #cf_span[m], #cf_span[k], #cf_span[q] (#cf_span[1 ≤ n, m, k, q ≤ 105]) —— 孩子数、玩具数、场景请求数和查询数。
接下来的 #cf_span[k] 行每行包含两个整数 #cf_span[a], #cf_span[b] (#cf_span[1 ≤ a ≤ n] 且 #cf_span[1 ≤ b ≤ m]) —— 表示一个场景请求，即孩子 #cf_span[a] 请求玩具 #cf_span[b]。请求按孩子们提出请求的顺序给出。
接下来的 #cf_span[q] 行每行包含两个整数 #cf_span[x], #cf_span[y] (#cf_span[1 ≤ x ≤ n] 且 #cf_span[1 ≤ y ≤ m]) —— 表示要添加到场景中的请求，即孩子 #cf_span[x] 将在拿到他正在等待的玩具后（如果有的话）请求玩具 #cf_span[y]。
保证场景请求一致，且初始时没有任何孩子在哭。所有场景请求互不相同，且没有任何查询与场景请求重复。
对于每个查询，请在单独一行上输出当孩子 #cf_span[x] 对玩具 #cf_span[y] 提出最后一个请求时，开始哭的孩子数量。请独立回答所有查询。
在第一个例子中，孩子 #cf_span[1] 正在等待玩具 #cf_span[2]，该玩具由孩子 #cf_span[2] 持有；孩子 #cf_span[2] 正在等待玩具 #cf_span[3]，该玩具由孩子 #cf_span[3] 持有。当孩子 #cf_span[3] 提出他的最后一个请求时，他请求的玩具被孩子 #cf_span[1] 持有。三个孩子中的每一个都在等待另一个孩子持有的玩具，且没有人正在玩，因此三个孩子都会开始哭。
在第二个例子中，最初，对于 #cf_span[1 ≤ i ≤ 4]，孩子 #cf_span[i] 持有玩具 #cf_span[i]。孩子 #cf_span[1] 和 #cf_span[3] 已完成他们的玩具集合。他们完成后，玩具 #cf_span[3] 将空闲，而玩具 #cf_span[1] 将被刚刚完成玩具集合的孩子 #cf_span[2] 拿走。他完成后，玩具 #cf_span[1] 和 #cf_span[2] 将空闲，孩子 #cf_span[5] 将拿走玩具 #cf_span[1]。现在：
## Input
第一行包含四个整数 #cf_span[n], #cf_span[m], #cf_span[k], #cf_span[q] (#cf_span[1 ≤ n, m, k, q ≤ 105]) —— 孩子数、玩具数、场景请求数和查询数。接下来的 #cf_span[k] 行每行包含两个整数 #cf_span[a], #cf_span[b] (#cf_span[1 ≤ a ≤ n] 且 #cf_span[1 ≤ b ≤ m]) —— 表示一个场景请求，即孩子 #cf_span[a] 请求玩具 #cf_span[b]。请求按孩子们提出请求的顺序给出。接下来的 #cf_span[q] 行每行包含两个整数 #cf_span[x], #cf_span[y] (#cf_span[1 ≤ x ≤ n] 且 #cf_span[1 ≤ y ≤ m]) —— 表示要添加到场景中的请求，即孩子 #cf_span[x] 将在拿到他正在等待的玩具后（如果有的话）请求玩具 #cf_span[y]。保证场景请求一致，且初始时没有任何孩子在哭。所有场景请求互不相同，且没有任何查询与场景请求重复。
## Output
对于每个查询，请在单独一行上输出当孩子 #cf_span[x] 对玩具 #cf_span[y] 提出最后一个请求时，开始哭的孩子数量。请独立回答所有查询。
[samples]
## Note
在第一个例子中，孩子 #cf_span[1] 正在等待玩具 #cf_span[2]，该玩具由孩子 #cf_span[2] 持有；孩子 #cf_span[2] 正在等待玩具 #cf_span[3]，该玩具由孩子 #cf_span[3] 持有。当孩子 #cf_span[3] 提出他的最后一个请求时，他请求的玩具被孩子 #cf_span[1] 持有。三个孩子中的每一个都在等待另一个孩子持有的玩具，且没有人正在玩，因此三个孩子都会开始哭。
在第二个例子中，最初，对于 #cf_span[1 ≤ i ≤ 4]，孩子 #cf_span[i] 持有玩具 #cf_span[i]。孩子 #cf_span[1] 和 #cf_span[3] 已完成他们的玩具集合。他们完成后，玩具 #cf_span[3] 将空闲，而玩具 #cf_span[1] 将被刚刚完成玩具集合的孩子 #cf_span[2] 拿走。他完成后，玩具 #cf_span[1] 和 #cf_span[2] 将空闲，孩子 #cf_span[5] 将拿走玩具 #cf_span[1]。现在：
在第一个查询中，孩子 #cf_span[5] 将拿走玩具 #cf_span[3]，他完成后，孩子 #cf_span[4] 可以开始玩。在第二个查询中，孩子 #cf_span[5] 将请求玩具 #cf_span[4]，该玩具由孩子 #cf_span[4] 持有；同时，孩子 #cf_span[4] 正在等待玩具 #cf_span[1]，而该玩具现在由孩子 #cf_span[5] 持有。他们两人都无法玩，因此都会开始哭。
**Definitions**
Let $ n, m, k, q \in \mathbb{Z}^+ $ denote the number of children, toys, scenario requests, and queries, respectively.
Let $ R = \{(a_i, b_i) \mid i \in \{1, \dots, k\}\} $ be the set of scenario requests, where child $ a_i $ requests toy $ b_i $.
Let $ G \subseteq \{1, \dots, n\} \times \{1, \dots, m\} $ be the *granting relation*: $ (a, b) \in G $ iff child $ a $ is currently holding toy $ b $.
Let $ W \subseteq \{1, \dots, n\} \times \{1, \dots, m\} $ be the *waiting relation*: $ (a, b) \in W $ iff child $ a $ has requested toy $ b $ but does not hold it (and is waiting).
For each child $ c \in \{1, \dots, n\} $, define:
- $ \text{held}(c) = \{ b \mid (c, b) \in G \} $ — the toy(s) child $ c $ is holding.
- $ \text{requested}(c) = \{ b \mid (c, b) \in R \cup Q \} $ — all toys child $ c $ has requested (including query).
- $ \text{waiting}(c) = \text{requested}(c) \setminus \text{held}(c) $ — toys child $ c $ is waiting for.
Define a directed graph $ D = (V, E) $:
- $ V = \{1, \dots, n\} $: nodes are children.
- $ E = \{ (c_1, c_2) \mid \exists b \in \text{waiting}(c_1) \text{ such that } (c_2, b) \in G \} $: edge $ c_1 \to c_2 $ iff $ c_1 $ is waiting for a toy held by $ c_2 $.
**Constraints**
1. $ 1 \le n, m, k, q \le 10^5 $
2. All scenario requests in $ R $ are distinct.
3. No query $ (x, y) $ coincides with any $ (a, b) \in R $.
4. Initially, no child is crying (i.e., $ D $ has no cycles).
5. For each query $ (x, y) $, we add the request $ (x, y) $ to $ R $, and update $ W $ and $ D $ accordingly.
**Objective**
For each query $ (x, y) $:
- Add $ (x, y) $ to $ R $, update $ \text{waiting}(x) $, and update $ D $ by adding edge $ x \to c $ if toy $ y $ is held by child $ c $.
- Compute the size of the **largest strongly connected component (SCC)** in the updated graph $ D $ that contains at least one edge (i.e., non-trivial SCC).
- Output the size of that SCC — this is the number of children who start crying.
API Response (JSON)
{
"problem": {
"name": "D. Sagheer and Kindergarten",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF812D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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:\n\n* Each child has a lovely set of toys that ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Sagheer 在一所幼儿园工作。有 #cf_span[n] 个孩子和 #cf_span[m] 种不同的玩具。这些孩子有明确的玩玩具协议：\n\n孩子们不喜欢互相玩。因此他们从不共享玩具。当一个孩子请求一个玩具时，是否将该玩具授予该孩子取决于该玩具是否空闲。如果玩具空闲，Sagheer 会将其交给孩子。否则，孩子必须等待，且不能请求其他玩具。\n\n孩子们很聪明，能判断自己是否将永远等待下去才能得到想要的...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m, k, q \\in \\mathbb{Z}^+ $ denote the number of children, toys, scenario requests, and queries, respectively. \nLet $ R = \\{(a_i, b_i) \\mid i \\in \\{1, \\dots, k\\}\\} $ be the ...",
"is_translate": false,
"language": "Formal"
}
]
}