题目背景

若干年之前，八云紫策划了第二次月面战争。

作为神社的巫女，灵梦自然有保护人间之里人类的职责。为了能够使得人类免受月面战争可能造成的影响，灵梦决定在博丽神社设立一个结界。

由于结界的影响范围有限，只能覆盖到博丽神社，于是灵梦决定将人间之里的所有居民迁入到神社中去。然而由于居民数目较多，灵梦在组织上出现了一些困难。这时，她找到了外界的你，希望你帮助她解决这个问题。

题目描述

人间之里可以看做一张 $n$ 个点 $m$ 条边的有向图，而博丽神社在点 $t$ 。然而由于时间差的原因，灵梦不能一次性获取所有居民的位置，于是她会依次受到 $k$ 条消息，每条信息包含一个节点 $x$。

• 如果 $x$ 号节点本来没有居民，那么灵梦得知了有一个居民在 $x$ 号节点。
• 如果 $x$ 号节点本来有居民，那么由于某些原因， $x$ 号节点现在没有居民了。

由于某些原因，在 $t$ 号节点也有可能存在居民。

每当得知一条新的消息后，灵梦都需要快速计算出居民的最快疏散时间，以便于合理安排（此时，你可以认为其他节点上没有居民）。同时为了避免拥挤，以及其他难以预料的困难，灵梦做出了如下规则：

• 每一时刻，每个居民只能沿着一条有向边走一步，或者停留在原地。
• 每一时刻，每个节点上，最多只能有一位居民。
• 当居民到达了博丽神社，那么下一时刻他就可以进入结界以获得庇护。你可以认为，在居民进入结界后他的行程就结束了。

最快疏散时间，指的是所有居民全部进入结界的最短用时。

输入格式

第一行四个正整数 $n,m,k,t$ ，含义如题所示。

接下来 $m$ 行，每行两个正整数 $u,v$ ，描述一条 $u\to v$ 的有向边。可能出现自环或者重边，请选手自行忽略。

接下来一行，共 $k$ 个整数 $x_i$ ，表示在第 $i$ 条消息中 $x_i$ 号节点是否有居民的情况发生了变化。

输出格式

输出共 $k$ 行，每行表示在按照前 $i$ 条消息，疏散所有居民所用的最小疏散时间。

7 7 4 1
2 1
3 1
4 2
5 2
6 1
7 6
3 2
7 1 2 3

3
3
3
4

提示

样例 1 说明

这张图描述了初始状态、第一次操作、第二次操作的情况。可以发现；

• 第一次操作后， $7$ 号节点最快通过 $7\to 6\to 1$ 到达神社，再花费 $1$ 单位时间进入神社，总共用时 $3$ 单位时间。
• 第二次操作后， $1$ 号节点花费 $1$ 时刻进入神社， $7$ 号节点仍然按照 $7\to 6\to 1$ 到达神社，并花费 $1$ 单位时间进入神社即可。总共花费 $3$ 单位时间。

这张图描述了第三次操作后的情况。

第一时刻， $1$ 进入神社， $2\to 1,7\to 6$ ；第二时刻， $1$ 进入神社， $6\to 1$ ；第三时刻所有人都进入了神社，于是总共花费 $3$ 单位时间。

这张图描述了第四次操作后的情况。

第一时刻， $1$ 进入神社， $3\to 1,7\to 6$ ， $2$ 不动；第二时刻， $1$ 进入神社， $2\to 1$ ， $6$ 不动。接下来花费 $2$ 时刻全部进入神社，于是总共花费 $4$ 单位时间。

样例 2,3

见下发附件。

数据范围及约定

$$\def{\bd}{\boldsymbol} \def{\a}{\texttt{A}} % 链的性质 \def{\b}{\texttt{B}} % 菊花图的性质 \def{\p}{\texttt{P}} % k为正的性质 \def{\n}{\text{无特殊限制}} \def{\l}{\hline} \def{\arraystretch}{1.5}\begin{array}{|c|c|c|c|c|}\l \textbf{数据点} & \bd{n} & \bd{m} & \bd{k} & \textbf{特殊性质} \cr\l 1\sim4 & n\le 8 & m\le 10 & k\le 10 & - \cr\l 5,6 & \n & m=n-1 & \n & \p,\a \cr\l 7,8 & \n & m=n-1 & \n & \p,\b \cr\l 9 & n\le 10^5 & m=n-1 & k\le 10^5 & \p \cr\l 10\sim 12 & n\le 10^3 & m\le 10^3 & k\le 10^3 & - \cr\l 13,14 & n\le 10^5 & m\le 10^5 & k\le 10^5 & \p \cr\l 15\sim 17 & n\le 10^5 & m\le 10^5 & k\le 10^5 & - \cr\l 18\sim 20 & \n & \n & \n & - \cr\l \end{array} $$

• 特殊性质 $\texttt{P}:$ 保证只存在出现居民的操作。
• 特殊性质 $\texttt{A}:$ 保证整张图是一条链，但不保证 $t$ 是链的一端。
• 特殊性质 $\texttt{B}:$ 保证除了 $t$ 以外的所有节点，都指向 $t$ 。

对于所有数据，满足 $1\le n\le 10^6; 1\le m\le 1.05\times 10^6;1\le k\le 10^6$ 。保证所有节点可以到达 $t$。