A11041. Sagheer and Kindergarten
编程题
普及/提高-
知识点
题目描述
The first line contains four integers $n$ , $m$ , $k$ , $q$ ( $1<=n,m,k,q<=10^{5}$ ) — 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.
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.
输入格式
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.
输出格式
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.
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
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
说明/提示
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.
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.