Fastest Evacuation

In this problem, you are given a directed graph (G) with (n) nodes and (m) edges. The shrine is located at node (t). Initially, Reimu does not know the positions of the residents. Instead, she receives (k) messages one by one. Each message contains a node (x). The update rule is as follows:

• If node \(x\) is currently empty, a resident appears at node \(x\).
• If node \(x\) already has a resident, that resident is removed (i.e. the node becomes empty).

Note that it is possible that there is a resident at the shrine (node (t)).

After receiving each message, Reimu must quickly compute the minimum evacuation time for all residents currently present. The evacuation process follows these rules:

1. At each time step, each resident can either move along one directed edge or stay in place.
2. At any time step, each node can contain at most one resident.
3. Once a resident reaches the shrine (node \(t\)), in the next time step they can enter the protective barrier and their journey ends.

The "fastest evacuation time" is defined as the minimum number of time steps required to evacuate all residents (i.e. for every resident to have entered the barrier). If there exists a resident that cannot reach the shrine, the answer is (-1).

A key observation is that if a resident is at a node with a shortest distance (d) (in terms of number of edges) to (t), then, ignoring conflicts, the optimal evacuation would require (d+1) time steps (extra step to enter the barrier). However, due to the constraint that no two residents may occupy the same node simultaneously, if multiple residents have the same or similar distances, they may need to delay. An optimal strategy is to sort the residents by their shortest distance (in descending order) and compute the answer as:

[ answer = \max_{0 \le i < r} (d_i + i) + 1, ]

where (r) is the number of residents and (d_i) is the shortest distance from the resident's node to (t). If there are no residents, the answer is (0). Remember to output the evacuation time after processing each message.

Your task is to implement this process efficiently.

Note: You can precompute the shortest distance from every node to (t) by reversing the edges and performing a breadth-first search (BFS).

inputFormat

The input begins with a single line containing four space-separated integers (n), (m), (t), and (k) representing the number of nodes, the number of edges, the shrine node, and the number of messages, respectively.

Then follow (m) lines, each containing two space-separated integers (u) and (v) indicating a directed edge from node (u) to node (v).

Then follow (k) lines, each containing a single integer (x) representing a message. For each message:

• If node \(x\) is empty, a resident is added at node \(x\).
• If node \(x\) already has a resident, the resident is removed from node \(x\).

Nodes are numbered from 1 to (n). It is guaranteed that all numbers are positive integers.

outputFormat

For each of the (k) messages, output on a separate line the minimum evacuation time after processing that message. If there exists any resident that cannot reach the shrine, output (-1) for that message. If there are no residents, output (0).

sample

3 3 3 3
1 2
1 3
2 3
1
2
1

2
3
2

</p>