Holiday Shopping

It's holiday season and you're looking to buy some last-minute rubber ducks for all your programming friends. You can't resort to buying the gifts online because you can't afford the shipping fees, so you'll have to go into your local shopping mall: Eastmeadow™. However, the mall is filled with other shoppers who are also trying to get their last-minute gifts. Because you don't like people have to maintain social distancing, you have to somehow navigate your way through the mall while maintaining a certain distance to all the other shoppers.

We can represent the layout of the mall as a graph of $N$ nodes numbered from 0 to $N-1$ (each node represents a 1x1 meter tile). Each node will have at least one edge to another node - you can travel between any two nodes that share an edge. Currently, you are on node $0$ (you've just bought your gifts) and you wish to reach node $N-1$ (the exit).

Some of the nodes are occupied by other shoppers - you must be at least $M$ edges away from any occupied node. Because you walk so fast that other people don't appear to move, you can assume that the other shoppers remain stationary forever. What is the fewest number of nodes you need to visit on your path to the exit?

Input Format

• The first line contains the numbers $N$ and $E$ - the number of nodes in the mall and the number of edges, respectively.
• Each of the next $E$ lines is of the form $a_i$ $b_i$, indicating that there is an edge between nodes $a_i$ and $b_i$.
• The next line contains the numbers $S$ and $M$ - the number of other shoppers in the mall, and the minimum distance you need to stay away from other shoppers.
  
• Each of the next $S$ lines contains a number $s_i$, indicating that the node $s_i$ is occupied.

Output Format

Output a single number - the fewest number of nodes you need to visit while maintaining distancing from the other shoppers. If it's impossible to reach the exit while maintaining distancing, output the string SELF_ISOLATE (without quotes) instead.
Note: It's possible that node 0 is closer than $M$ edges to an occupied node. In that case, you should still output SELF_ISOLATE.

Constraints

For all subtasks:

• $2 \le N \le 100,000$
• $1 \le E \le 100,000$
• $0 \le S \lt N$
• $0 \le M \le N$
• $1 < s_i < N-1$ for all $i$

Subtasks

• Subtask 1 (+35%): $S = 0$.
• Subtask 2 (+35%): $M \le 1$.
• Subtask 3 (+30%): No further constraints apply.

Sample Explanations

Sample 1

In this case, there are no other shoppers, so you can just go from node 0 -> node 1 -> node 4.

Sample 2

In this case, you must keep at least 1 edge away from node 1 (i.e. you can't go on node 1). The only way to reach the exit is to go from node 1 -> node 3 -> node 2 -> node 4.

Sample 3

In this case, it is impossible to get from node 0 to node 4 whilst staying more than 3 or more edges away from node 3.

Note: Python submissions should use Python 3.6 (PyPy 7.3), as submissions using Python 3.8 may not be fast enough to pass some subtasks.