ccf#NOI2021C. 庆典 (Celebration)
庆典 (Celebration)
Description
Ceres is a prosperous country. It consists of cities and directed roads, with cities numbered from to . If starting from city , city could be reached by moving along several roads, then we claim that city is reachable from city , denoted as . Roads in Ceres follow a particular pattern: for three cities , if and , then or .
It is one month from the millennial anniversary of the foundation of Ceres, and people of Ceres are preparing a grand ceremonial parade. The country of Ceres knows that there are parade plans, with the th parade wishing to start from city and end in city after passing through several cities. Within a parade, a city could be passed through multiple times. To make parades more enjoyable, for each parade directed roads will be temporarily built specially for that parade. In other words, other parade plans couldn't pass through roads built for that parade.
Now the country of Ceres wants to know the number of cities possibly passed through in each parade plan.
Note: Temporarily built roads don't necessarily follow the pattern of original roads in Ceres.
Input Format
The first line contains four integers , each indicating the number of cities, roads, parade plans and temporary roads for each parade. The following lines each contains two integers , representing a directed road .
For the following lines, they begin with two integers , representing the starting and end points for each parade; this is followed by pairs of integers in the line, each pair indicating a temporarily added directed road .
It is guaranteed that if all original directed roads in Ceres are deemed as undirected ones, then all cities are connected.
Output Format
For each query, output a line of one integer indicating the answer. If a parade could not reach the end point from the starting point, simply output .
5 6 4 1
1 2
1 3
1 4
2 5
4 5
5 4
1 4 5 1
2 3 5 3
1 2 5 2
3 4 5 1
4
4
4
0
Sample Explanation 1
The st plan, starting at point and ending in point , with a temporarily built road , could possibly pass through cities .
The nd plan, starting at point and ending in point , with a temporarily built road , could possibly pass through cities .
The rd plan, starting at point and ending in point , with a temporarily built road , could possibly pass through cities .
The th plan, starting at point and ending in point , with a temporarily built road , could not arrive in point from point .
Sample 2
See files celebration2.in and celebration2.ans under participant directory.
Constraints of this sample is the same as tests .
Sample 3
See files celebration3.in and celebration3.ans under participant directory.
Constraints of this sample is the same as tests .
Sample 4
See files celebration4.in and celebration4.ans under participant directory.
Constraints of this sample is the same as tests .
Sample 4
See files celebration5.in and celebration5.ans under participant directory.
Constraints of this sample is the same as tests .
Constraints and Specification
For all the tests, , , .
Test Number | Special Case | ||
---|---|---|---|