P10304 [THUWC 2020] Road Construction

Country $A$ is an ancient nation. There are $n$ cities in this country, numbered from $1$ to $n$. City $1$ is the capital, and it is also the only city with a port. Imported goods enter through the capital’s port and are then transported to other cities. To make the transportation of imported goods easier, the king of Country $A$ plans to build some one-way roads specifically for transporting goods. Soon, the ministers of Country $A$ proposed a road construction plan: the plan consists of $m$ one-way roads, and using these roads, one can travel from City $1$ to any other city in the country. Very specially, the road network formed by these $m$ roads has no cycles. Due to limited finances, the king of Country $A$ plans to first choose $n - 1$ roads from the $m$ roads to build, to ensure basic transportation capacity. He uses a method similar to depth-first search to determine the $n - 1$ roads to be built with higher priority: First, let the set $S$ contain only City $1$, and set the current city $u$ to be City $1$. Then, choose a road that starts from the current city $u$ and ends at a city $v$ that is not in set $S$. Mark this road as a priority road to be built, add city $v$ into set $S$, and set the parent of city $v$ to be the current city $u$. Finally, change the current city $u$ to city $v$. If there are multiple choices for city $v$, choose the one with the smallest city index; if there is no selectable city $v$, then change the current city $u$ to the parent of $u$. Repeat the above operations until all cities have been added into set $S$, then stop. It can be seen that the above steps select exactly $n - 1$ priority roads, and these priority roads form a tree structure rooted at the capital. We call these priority roads the tree roads. As the economy develops, Country $A$ gradually completes the entire road network consisting of the $m$ roads. However, the tree roads, since they were built earlier, often need maintenance. The ministers of Country $A$ proposed $q$ possible maintenance plans. Each maintenance plan requires maintaining all tree roads between city $a$ and city $b$, and it is guaranteed that city $a$ is an ancestor of city $b$ in the tree. Such a maintenance plan will have a large impact on the subtree rooted at city $b$. The king of Country $A$ wants you to evaluate each possible maintenance plan: compute, when all tree roads between city $a$ and city $b$ are unusable, how many cities in the subtree rooted at city $b$ will become unreachable from the capital?

The first line contains three integers $n, m, q$, representing the number of cities in Country $A$, the number of roads in the construction plan, and the number of maintenance plans. The next $m$ lines each contain two integers $x, y$, indicating a one-way road from $x$ to $y$ in the construction plan. The next $q$ lines each contain two integers $a, b$, indicating a maintenance plan. The input guarantees that: 1. The given construction plan ensures that every city in Country $A$ is reachable from the capital, and there are no cycles in the plan. 2. Between any two cities, there is at most one road, and the endpoints of each road have different city indices. 3. In each maintenance plan, city $a$ is guaranteed to be some ancestor of city $b$ in the tree structure formed by the tree roads.

Output $q$ lines, each containing one integer, indicating for each maintenance plan how many cities in the subtree rooted at city $b$ will be unreachable from the capital.

**Subtasks** |Subtask ID|Score|Special Constraints| |:----:|:----:|:----:| |$1$|$20$|$n, q \leq 1000$, $m \leq 1500$| |$2$|$23$|It is guaranteed that in each maintenance plan, city $a$ is the parent of city $b$.| |$3$|$11$|$m = n$| |$4$|$19$|It is guaranteed that the maintenance plans satisfy $a = 1$.| |$5$|$27$|None.| For $100\%$ of the data, $1 \leq n, q \leq 10^5$, $1 \leq m \leq 1.5 \times 10^5$. Translated by ChatGPT 5