Problem Description

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.

Input Format

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.

Output Format

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$.

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

Hint

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$.

Translated by ChatGPT 5