#1856. 「NOI2021」庆典

「NOI2021」庆典

题面描述

C 国是一个繁荣昌盛的国家,它由 nn 座城市和 mm 条有向道路组成,城市从 11nn 编号。如果从 xx 号城市出发,经过若干条道路后能到达 yy 号城市,那么我们称 xx 号城市可到达 yy 号城市,记作 xyx \Rightarrow y。C 国的道路有一个特点:对于三座城市 x, y, zx,~y,~z,若 xzx \Rightarrow zyzy \Rightarrow z,那么有 xyx \Rightarrow yyxy \Rightarrow x

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

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

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

输入格式

从文件 celebration.in 中读入数据。

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

接下来 mm 行,每行包含两个整数 u, vu,~v,表示一条有向道路 uvu \rightarrow v。 接下来 qq 行,每行前两个整数 si,tis_i, t_i,表示每次游行的起点与终点;这行接下来有 kk 对整数 a, ba,~b,每对整数表示一条临时添加的有向道路 aba \rightarrow b。 数据保证,将 C 国原有的有向道路视为无向道路后,所有城市可以互达。

输出格式

输出到文件 celebration.out 中。

对于每次询问,输出一行一个整数表示答案。如果一次游行从起点出发无法到达终点,输出 00 即可。

样例 1

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

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

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

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

第四次计划,起点为 33 号点,终点为 44 号点,临时修建道路为 515 \rightarrow 1,最终从 33 号点出发无法到达 44 号点。

大样例

样例 2 见附加文件的 celebration2.incelebration2.ans。该样例约束与测试点 5 ∼ 7 一致。

样例 3 见附加文件的 celebration3.incelebration3.ans。该样例约束与测试点 10 ∼ 11 一致。

样例 4 见附加文件的 celebration4.incelebration4.ans。该样例约束与测试点 15 ∼ 16 一致。

样例 5 见附加文件的 celebration5.incelebration5.ans。该样例约束与测试点 20 ∼ 25 一致。

数据范围与提示

对于 100%100\% 的数据,有 1n, q3×105, 1\le n,~q \le 3\times 10^5,~n1m6×105, n-1\le m\le 6\times 10^5,~0k20\le k\le 2

测试点编号 n, qn,~q\le kk 特殊性质
1 ~ 4 55 =0=0
5 ~ 7 10001000 2\le 2
8 ~ 9 3×1053\times 10^5 =0=0 m=n1m=n-1
10 ~ 11 =1=1
12 ~ 14 =2=2
15 ~ 16 =0=0
17 ~ 19 =1=1
20 ~ 25 =2=2