Description

The Human Village can be viewed as a directed graph with $n$ nodes and $m$ edges, and the Hakurei Shrine is at node $t$. However, due to the time difference, Reimu cannot obtain all residents' positions at once, so she will receive $k$ messages in order, and each message contains a node $x$.

• If node $x$ originally has no resident, then Reimu learns that there is a resident at node $x$.
• If node $x$ originally has a resident, then for some reason, node $x$ now has no resident.

For some reason, there may also be residents at node $t$.

After learning each new message, Reimu needs to quickly compute the fastest evacuation time for the residents, in order to make reasonable arrangements (at this time, you may assume there are no residents on other nodes). To avoid congestion and other unpredictable difficulties, Reimu sets the following rules:

• At each moment, each resident can move one step along one directed edge, or stay where they are.
• At each moment, at each node, there can be at most one resident.
• When a resident arrives at the Hakurei Shrine, then in the next moment they can enter the barrier to receive shelter. You may assume that after a resident enters the barrier, their journey ends.

The fastest evacuation time refers to the minimum time needed for all residents to enter the barrier.

Input Format

The first line contains four positive integers $n, m, k, t$, with meanings as described above.

The next $m$ lines each contain two positive integers $u, v$, describing a directed edge $u\to v$. Self-loops or multiple edges may appear; please ignore them by yourself.

The next line contains $k$ integers $x_i$, meaning that in the $i$-th message, the resident status of node $x_i$ changes.

Output Format

Output $k$ lines in total. The $i$-th line represents the minimum evacuation time to evacuate all residents after applying the first $i$ messages.

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

Hint

Explanation for Sample 1

This figure shows the initial state, the first operation, and the second operation. We can see that:

• After the first operation, node $7$ reaches the shrine fastest via $7\to 6\to 1$, and then spends $1$ unit of time to enter the shrine, for a total time of $3$ units.
• After the second operation, node $1$ spends $1$ moment to enter the shrine, and node $7$ still reaches the shrine via $7\to 6\to 1$, then spends $1$ unit of time to enter the shrine. The total time is $3$ units.

This figure shows the situation after the third operation.

At the first moment, $1$ enters the shrine, $2\to 1, 7\to 6$; at the second moment, $1$ enters the shrine, $6\to 1$; at the third moment, everyone has entered the shrine, so the total time is $3$ units.

This figure shows the situation after the fourth operation.

At the first moment, $1$ enters the shrine, $3\to 1, 7\to 6$, and $2$ does not move; at the second moment, $1$ enters the shrine, $2\to 1$, and $6$ does not move. Then it takes $2$ more moments for everyone to enter the shrine, so the total time is $4$ units.

Samples 2 and 3

See the attached files provided.

Constraints and Notes

$$\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}$$

• Special property $\texttt{P}$: It is guaranteed that there are only operations that make residents appear.
• Special property $\texttt{A}$: It is guaranteed that the whole graph is a chain, but it is not guaranteed that $t$ is an endpoint of the chain.
• Special property $\texttt{B}$: It is guaranteed that all nodes except $t$ point to $t$.

For all testdata, it holds that $1\le n\le 10^6; 1\le m\le 1.05\times 10^6; 1\le k\le 10^6$. It is guaranteed that all nodes can reach $t$.

Translated by ChatGPT 5