3600. [NOI 2021]庆典

【题目描述】

C国是一个繁荣昌盛的国家，它由$n$座城市和$m$条有向道路组成，城市由$1$到$n$编号。如果从$x$号城市出发，经过若干条道路后能到达$y$号城市，那么我们称$x$号城市可到达$y$号城市，记作$x \Rightarrow y$。 C国的道路有一个特点：对于三座城市$x,y,z$，若$x \Rightarrow z $且$y \Rightarrow z$，那么有$x \Rightarrow y$或$y \Rightarrow x$

再过一个月就是C国成立的千年纪念日，所以C国的人民正在筹备盛大的游行庆典。目前C国得知接下来会有$q$次游行计划，第$i$次游行希望从城市$s_i$出发,经过若干个城市之后，在城市$t_i$结束，且在游行过程中，一个城市可以被经过多次。为了增加游行的乐趣，每次游行还会临时修建出$k(0 \leq k \leq 2)$条有向道路专门供本次游行使用，即其他旅行计划不能通过本次游行修建的道路。

现在C国想知道，每次游行计划可能会经过多少座城市。

注意：临时修建出的道路可以不满足 C 国道路原有的特点。

【输入格式】

第一行包含四个整数$n,m,q,k$，分别表示城市数、道路数、游行计划数以及每次游行临时修建的道路数。

接下来$m$行，每行包含两个整数$u,v$，表示一条有向道路$u \rightarrow v$。

接下来$q$行，每行两个整数$s_i,t_i$，表示每次游行的起点与终点；这行接下来有$k$对整数$a,b$，每对整数表示一条临时添加的有向道路$a \rightarrow b$

数据保证，将 C 国原有的有向道路视为无向道路后，所有城市可以互达。

【输出格式】

对于每次询问，输出一行一个整数表示答案。如果一次游行从起点出发无法到达终点，输出$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

【样例说明】

第 $1$ 次计划，起点为 $1$ 号点，终点为 $4$ 号点，临时修建道路为$ 5 \rightarrow 1$，最终可能经过的城市编号为 $\{1,2,4,5\}$。

第 $2$ 次计划，起点为 $2$ 号点，终点为 $3$ 号点，临时修建道路为$ 5 \rightarrow 3$，最终可能经过的城市编号为 $\{2,3,4,5\}$。

第 $3$ 次计划，起点为 $1$ 号点，终点为 $2$ 号点，临时修建道路为$ 5 \rightarrow 2$，最终可能经过的城市编号为 $\{1,2,4,5\}$。

第 $4$ 次计划，起点为 $3$ 号点，终点为 $4$ 号点，临时修建道路为$ 5 \rightarrow 1$，最终从$3$号点出发无法达到$4$号点。

【其他测试样例】

其他测试样例下载

注意：第二个样例约束条件与5-7相同

    第三个样例约束条件与10-11相同

    第四个样例约束条件与15-16相同

    第五个样例约束条件与20-25相同

【数据规模与约定】

对于所有测试点，$1\leq n,q\leq 3\times 10^5,n-1\leq m\leq 6\times 10^5,0\leq k\leq 2$。

【题目来源】

NOI2021 Day1 Task3