题目描述

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

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

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

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

输入格式

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

第一行包含四个整数 $n, m, q, k$，分别表示城市数、道路数、游行计划数以及每次游行临时修建的道路数。接下来 $m$ 行，每行包含两个整数 $u, v$，表示一条有向道路 $u → v$。

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

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

输出格式

输出到文件 celebration.out 中。

对于每次询问，输出一行一个整数表示答案。如果一次游行从起点出发无法到达终点，输出 $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$ 次计划，起点为 $1$ 号点，终点为 $4$ 号点，临时修建道路为 $5 → 1$，最终可能经 过的城市编号为 $\{1, 2, 4, 5\}$。

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

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

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

样例 2

见选手目录下的 celebration2.in 与 celebration2.ans。

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

样例 3

见选手目录下的 celebration3.in 与 celebration3.ans。

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

样例 4

见选手目录下的 celebration4.in 与 celebration4.ans。

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

样例 5

见选手目录下的 celebration5.in 与 celebration5.ans。

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

数据规模与约定

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