Celebration

rpeng: I raised the TL to 2 seconds to avoid fast I/O nonsense. I was able to get AC (very close though) using cin/cout.

There are $n$ cities and $m$ one-directional roads in a country. The cities are numbered $1, 2, \dots, n$. If it is possible to reach city $y$ via roads from city $x$, we say city $y$ is reachable from city $x$, denoted $x \Rightarrow y$. The roads in the country satisfy the following property: for three cities $x,y,z$, if $x \Rightarrow z$ and $y \Rightarrow z$, then $x \Rightarrow y$ or $y \Rightarrow x$.

There will be $q$ parades during the celebration. The $i$-th parade starts in city $s_i$ and ends in city $t_i$ after visiting some other cities. A city may be visited multiple times during a parade. To make the parades more interesting, for each parade we build $k$ $(0 \le k \le 2)$ one-way roads for the exclusive use of that parade. Other parades may not use the roads built for a specific parade.

Now we want to know the number of cities that could be visited during a parade. Note that roads built for the exclusive use of a parade do not have to satisfy the property satisfied by the roads originally in the country.

The first line contains four integers $n, m, q, k$, the number of cities, the number of roads, the number of parades, and the number of roads built for each parade.

The following $m$ lines each contain two integers $u, v$, meaning there is a one-way road $u \rightarrow v$.

The next $q$ lines each contain two integers $s_i, t_i$, the origin and the destination of the parade. On the same line, there are $k$ pairs of integers $a, b$, meaning there is a temporary one-way road $a \rightarrow b$ for the exclusive use of that parade.

If the original roads are treated as bidirectional, all cities are mutually reachable.

For each parade, output the answer on its own line. The answer is the number of cities that could be visited. If the destination cannot be reached from the origin, output 0.

For all test cases, $1 \le n, q \le 3 \times 10^5$, $n-1 \le m \le 6 \times 10^5$, and $0 \le k \le 2$.

In parade 1, the origin is city 1 and the destination is city 4. The temporary road is $5 \rightarrow 1$. The cities that may be visited are 1, 2, 4, and 5.

In parade 2, the origin is city 2 and the destination is city 3. The temporary road is $5 \rightarrow 3$. The cities that may be visited are 2, 3, 4, and 5.

In parade 3, the origin is city 1 and the destination is city 2. The temporary road is $5 \rightarrow 2$. The cities that may be visited are 1, 2, 4, and 5.

In parade 4, the origin is city 3 and the destination is city 4. The temporary road is $5 \rightarrow 1$. City 4 cannot be reached from city 3.