UOJ Logo Universal Online Judge

UOJ

#675. 【NOI2021】庆典

附件下载 统计

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$ 即可。

样例一

input

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

output

4
4
4
0

explanation

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

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

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

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

样例二

见附加文件的 celebration2.incelebration2.ans

该样例约束与测试点 $5 \sim 7$ 一致。

样例三

见附加文件的 celebration3.incelebration3.ans

该样例约束与测试点 $10 \sim 11$ 一致。

样例四

见附加文件的 celebration4.incelebration4.ans

该样例约束与测试点 $15 \sim 16$ 一致。

样例五

见附加文件的 celebration5.incelebration5.ans

该样例约束与测试点 $20 \sim 25$ 一致。

测试点约束

对于 $100\%$ 的数据,有 $1\le n,~q \le 3\times 10^5,~$$n-1\le m\le 6\times 10^5,~$$0\le k\le 2$。

测试点编号 $n,~q\le$ $k$ 特殊性质
$1 \sim 4$ $5$ $=0$
$5 \sim 7$ $1000$ $\le 2$
$8 \sim 9$ $3\times 10^5$ $=0$ $m=n-1$
$10 \sim 11$ $3\times 10^5$ $=1$ $m=n-1$
$12 \sim 14$ $3\times 10^5$ $=2$ $m=n-1$
$15 \sim 16$ $3\times 10^5$ $=0$
$17 \sim 19$ $3\times 10^5$ $=1$
$20 \sim 25$ $3\times 10^5$ $=2$

时间限制:$\require{cancel}\cancel{1\texttt{s}}2\texttt{s}$

空间限制:$1\texttt{GB}$