ccf#NOI2021C. 庆典 (Celebration)

庆典 (Celebration)

Description

Ceres is a prosperous country. It consists of nn cities and mm directed roads, with cities numbered from 11 to nn. If starting from city xx, city yy could be reached by moving along several roads, then we claim that city yy is reachable from city xx, denoted as xyx \Rightarrow y. Roads in Ceres follow a particular pattern: for three cities x,y,zx,y,z, if xzx \Rightarrow z and yzy \Rightarrow z, then xyx \Rightarrow y or yxy \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 qq parade plans, with the iith parade wishing to start from city sis_i and end in city tit_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(0k2)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,kn,m,q,k, each indicating the number of cities, roads, parade plans and temporary roads for each parade. The following mm lines each contains two integers u,vu,v, representing a directed road uvu \rightarrow v.

For the following qq lines, they begin with two integers si,tis_i,t_i, representing the starting and end points for each parade; this is followed by kk pairs of integers a,ba,b in the line, each pair indicating a temporarily added directed road aba \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 00.

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 11st plan, starting at point 11 and ending in point 44, with a temporarily built road 515 \rightarrow 1, could possibly pass through cities {1,2,4,5}\{ 1,2,4,5 \}.

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

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

The 44th plan, starting at point 33 and ending in point 44, with a temporarily built road 515 \rightarrow 1, could not arrive in point 44 from point 33.

Sample 2

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

Sample 3

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

Sample 4

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

Sample 4

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

Constraints and Specification

For all the tests, 1n,q3×1051 \leq n,q \leq 3 \times 10^5, n1m6×105n-1 \leq m \leq 6 \times 10^5, 0k20 \leq k \leq 2.

Test Number n,qn,q \leq kk Special Case
141 \sim 4 55 =0=0 None\text{None}
575 \sim 7 10001000 2\leq 2
898 \sim 9 3×1053 \times 10^5 =0=0 m=n1m=n-1
101110 \sim 11 =1=1
121412 \sim 14 =2=2
151615 \sim 16 =0=0 None\text{None}
171917 \sim 19 =1=1
202520 \sim 25 =2=2