Description

Ceres is a prosperous country. It consists of $n$ cities and $m$ directed roads, with cities numbered from $1$ to $n$. If starting from city $x$, city $y$ could be reached by moving along several roads, then we claim that city $y$ is reachable from city $x$, denoted as $x \Rightarrow y$. Roads in Ceres follow a particular pattern: for three cities $x,y,z$, if $x \Rightarrow z$ and $y \Rightarrow z$, then $x \Rightarrow y$ or $y \Rightarrow x$.

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 $q$ parade plans, with the $i$th parade wishing to start from city $s_i$ and end in city $t_i$ after passing through several cities. Within a parade, a city could be passed through multiple times. To make parades more enjoyable, for each parade $k(0 \leq k \leq 2)$ 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 $n,m,q,k$, each indicating the number of cities, roads, parade plans and temporary roads for each parade. The following $m$ lines each contains two integers $u,v$, representing a directed road $u \rightarrow v$.

For the following $q$ lines, they begin with two integers $s_i,t_i$, representing the starting and end points for each parade; this is followed by $k$ pairs of integers $a,b$ in the line, each pair indicating a temporarily added directed road $a \rightarrow b$.

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

Sample Explanation 1

The $1$st plan, starting at point $1$ and ending in point $4$, with a temporarily built road $5 \rightarrow 1$, could possibly pass through cities $\{ 1,2,4,5 \}$.

The $2$nd plan, starting at point $2$ and ending in point $3$, with a temporarily built road $5 \rightarrow 3$, could possibly pass through cities $\{ 2,3,4,5 \}$.

The $3$rd plan, starting at point $1$ and ending in point $2$, with a temporarily built road $5 \rightarrow 2$, could possibly pass through cities $\{ 1,2,4,5 \}$.

The $4$th plan, starting at point $3$ and ending in point $4$, with a temporarily built road $5 \rightarrow 1$, could not arrive in point $4$ from point $3$.

Sample 2

See files celebration2.in and celebration2.ans under participant directory.
Constraints of this sample is the same as tests $5 \sim 7$.

Sample 3

See files celebration3.in and celebration3.ans under participant directory.
Constraints of this sample is the same as tests $10 \sim 11$.

Sample 4

See files celebration4.in and celebration4.ans under participant directory.
Constraints of this sample is the same as tests $15 \sim 16$.

Sample 4

See files celebration5.in and celebration5.ans under participant directory.
Constraints of this sample is the same as tests $20 \sim 25$.

Constraints and Specification

For all the tests, $1 \leq n,q \leq 3 \times 10^5$, $n-1 \leq m \leq 6 \times 10^5$, $0 \leq k \leq 2$.