P7737 [NOI2021] Celebration

Country C is a prosperous nation. It consists of $n$ cities and $m$ directed roads, with cities numbered from $1$ to $n$. If starting from city $x$ and traveling along some roads can reach city $y$, then we say city $x$ can reach city $y$, denoted as $x\Rightarrow y$. The roads in Country C have a special property: for three cities $x$, $y$, $z$, if $x\Rightarrow z$ and $y\Rightarrow z$, then $x\Rightarrow y$ or $y\Rightarrow x$ holds. In one month, it will be the millennium anniversary of the founding of Country C, so its people are preparing a grand parade celebration. Country C has learned that there will be $q$ parade plans. In the $i$-th parade, they want to start from city $s_i$, pass through some cities, and end at city $t_i$, and during the parade, **a city may be visited multiple times**. To make the parade more fun, each parade will also **temporarily** build $k$ ($0 \le k \le 2$) directed roads that are only for this parade, meaning other parade plans cannot use the roads built for this parade. Now Country C wants to know, for each parade plan, how many cities it may **possibly pass through**. Note: The temporarily built roads **may not satisfy the original special property** of Country C's roads.

The first line contains four integers $n,m,q,k$, representing the number of cities, the number of roads, the number of parade plans, and the number of temporarily built roads for each parade. The next $m$ lines each contain two integers $u,v$, indicating a directed road $u\rightarrow v$. The next $q$ lines describe the queries. Each line starts with two integers $s_i,t_i$, indicating the start city and end city of the parade; then there are $k$ pairs of integers $a,b$, where each pair indicates a temporarily added directed road $a\rightarrow b$. The testdata guarantees that if the original directed roads of Country C are viewed as undirected edges, then all cities are mutually reachable.

For each query, output one line with one integer as the answer. If in a parade it is impossible to reach the end city from the start city, output $0$.

**Sample Explanation #1** In the $1$-st plan, the start city is $1$ and the end city is $4$. The temporarily built road is $5\rightarrow1$. The cities that may finally be passed through are $\{1,2,4,5\}$. In the $2$-nd plan, the start city is $2$ and the end city is $3$. The temporarily built road is $5\rightarrow3$. The cities that may finally be passed through are $\{2,3,4,5\}$. In the $3$-rd plan, the start city is $1$ and the end city is $2$. The temporarily built road is $5\rightarrow2$. The cities that may finally be passed through are $\{1,2,4,5\}$. In the $4$-th plan, the start city is $3$ and the end city is $4$. The temporarily built road is $5\rightarrow1$. Finally, it is impossible to reach city $4$ starting from city $3$. **Sample #2** See the attachments `celebration/celebration2.in` and `celebration/celebration2.ans`. This sample has the same constraints as test points $5 \sim 7$. **Sample #3** See the attachments `celebration/celebration3.in` and `celebration/celebration3.ans`. This sample has the same constraints as test points $10 \sim 11$. **Sample #4** See the attachments `celebration/celebration4.in` and `celebration/celebration4.ans`. This sample has the same constraints as test points $15 \sim 16$. **Sample #5** See the attachments `celebration/celebration5.in` and `celebration/celebration5.ans`. This sample has the same constraints as test points $20 \sim 25$. **Constraints** For all test points, $1 \le n,q \le 3 \times {10}^5$, $n - 1 \le m \le 6 \times {10}^5$, $0 \le k \le 2$. | Test Point ID | $n, q \le$ | $k$ | Special Property | |:-:|:-:|:-:|:-:| | $1 \sim 4$ | $5$ | $= 0$ | None | | $5 \sim 7$ | $1000$ | $\le 2$ | None | | $8 \sim 9$ | $3 \times {10}^5$ | $= 0$ | $m = n - 1$ | | $10 \sim 11$ | $3 \times {10}^5$ | $= 1$ | $m = n - 1$ | | $12 \sim 14$ | $3 \times {10}^5$ | $= 2$ | $m = n - 1$ | | $15 \sim 16$ | $3 \times {10}^5$ | $= 0$ | None | | $17 \sim 19$ | $3 \times {10}^5$ | $= 1$ | None | | $20 \sim 25$ | $3 \times {10}^5$ | $= 2$ | None | Translated by ChatGPT 5