题目背景

English Statement. You must submit your code at the Chinese version of the statement.

本场比赛所有题目从标准输入读入数据，输出到标准输出。

题目描述

巡准备了一场超级演出。舞台和候场室可以看作一个包含 $n$ 个点 $m$ 条边的有向图，并且这个图当中没有环，也就是说，这是一张有向无环图（DAG）。

舞台为 $1$ 号节点，保证所有节点均有到达节点 $\bm 1$ 的路径。其余的节点均为候场室，每个候场室恰有一个剧团进行等待。

巡可以对一个候场室 $u$ 发布出场命令：

• 如果这个候场室的剧团还没有出场，并且存在一条 $u\to 1$ 的路径上没有其余候场的剧团。那么这个剧团就会沿着这条路径到达舞台进行演出，随后退场。注意：一个剧团退场后不会重新回到候场室。
• 否则，这个命令被认为是无效的。

巡有一个命令序列 $a_1,a_2,\dots,a_k$ 和 $q$ 次询问，每次给出一个区间 $[l,r]$。巡想要知道如果依次对候场室 $a_l,a_{l+1},\dots,a_r$ 发布出场命令后，候场室还会剩下多少剧团等待演出。

注意：每次询问相互独立，也就是说，每次询问之前，每个候场室都恰有一个剧团进行等待。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。

第二行包含四个正整数 $n,m,k,q$，表示图的点数，边数，序列长度，和询问次数。

接下来 $m$ 行，每行两个正整数 $u,v$，表示一条从 $u$ 到 $v$ 的有向边。保证无自环，无重边。

接下来的一行，$k$ 个正整数 $a_1,a_2,\dots,a_k$。

接下来 $q$ 行，每行两个正整数 $l,r$，表示一次询问的区间。

输出格式

输出到标准输出。

$q$ 行，每行一个非负整数，表示一次询问的答案。

0
5 5 5 4
2 1
3 1
5 1
4 2
4 3
2 4 4 3 5
1 2
1 5
3 5
2 3

2
0
2
4

提示

【样例 1 解释】

如图：

• 当询问 $l=1,r=2$ 时：

  • 发布出场命令 $a_1=2$。$2$ 沿着 $2\to 1$ 出场。
  • 发布出场命令 $a_2=4$。$4$ 沿着 $4\to 2\to 1$ 出场。

  此时余下 $3,5$ 两个剧团，输出 $2$。

• 当询问 $l=2,r=3$ 时：

  • 发布出场命令 $a_2=4$。找不到 $4\to 1$ 的且路上没有别的剧团的路线，该指令被认为无效。
  • 发布出场命令 $a_3=4$。找不到 $4\to 1$ 的且路上没有别的剧团的路线，该指令被认为无效。

  此时余下 $2,3,4,5$ 四个剧团，输出 $4$。

【样例 2】

见选手目录下的 show/show2.in 与 show/show2.ans。

这个样例满足测试点 $1,2$ 的限制条件。

【样例 3】

见选手目录下的 show/show3.in 与 show/show3.ans。

这个样例满足测试点 $5\sim 8$ 的限制条件。

【样例 4】

见选手目录下的 show/show4.in 与 show/show4.ans。

这个样例满足测试点 $9\sim 11$ 的限制条件。

【样例 5】

见选手目录下的 show/show5.in 与 show/show5.ans。

这个样例满足测试点 $12,13$ 的限制条件。

【样例 6】

见选手目录下的 show/show6.in 与 show/show6.ans。

这个样例满足测试点 $18,19$ 的限制条件。

---

【数据范围】

对于全部的测试数据，保证：

• $1\leq n,k,q\leq2\times10^5$；
• $1\leq m\leq4\times10^5$；
• $1\leq v<u\leq n$，且不存在两组相同的 $(u,v)$；
• 对于任意 $1\le i\le k$，$2\leq a_i\leq n$；
• 对于每组询问，$1\leq l\leq r\leq k$；
• 输入构成一张有向无环图，且所有节点均存在到达节点 $1$ 的路径。

测试点	$n,k,q\leq$	$m\leq$	特殊性质
$1,2$	$300$	$600$	无
$3,4$	$2\,000$	$4\,000$	A
$5\sim 8$			无
$9\sim 11$	$2\times10^5$	$4\times10^5$	A
$12,13$			BC
$14,15$			C
$16,17$			BD
$18,19$			D
$20\sim 22$			B
$23\sim 25$			无

• 特殊性质 A：图退化为一棵内向树，也就是说，除节点 $1$ 外，每个点恰有一条出边，节点 $1$ 没有出边；
• 特殊性质 B：保证对于每组询问，$r=k$；
• 特殊性质 C：保证对于任意 $1\leq i< j\leq k$，$a_i\neq a_j$；
• 特殊性质 D：保证每个点的入度和出度均不超过 $30$。