Shady Suburbs

Problem Statement

Will is trying to get home after a long day of work at university. Unfortunately for him, it's already 3am, and there are a lot shady people hiding at the end of some roads ready to jump on Will.

You are given a list of places that are shady, and a list of all roads in Melbourne. How many roads will Will have to cross before getting home?

Input

Your first line will contain $v$ and $e$ as space-separated integers. $v$ represents the number of suburbs in Melbourne, labelled from $0$ to $v-1$, and $e$ represents the number of roads in Melbourne.

Your next line will contain $a$ and $b$ as space-separated integers, indicating the locations of the university and Will's home.

Your next line will contain integer $s$, indicating the total number of shady suburbs in Melbourne.

Your next line will contain $b$ space-separataed integers, each representing a suburb that is shady.

Your next $e$ lines will contain $2$ space-separated numbers, specifying a road between the two suburbs.

Output

A single integer, representing the number of roads Will must cross before getting home without heading to any shady suburbs.

If no such path is possible, output $-1$ instead.

Constraints

For all test cases:

• $2 \le v \le 10^3$
• $0 \le s \le v$
• $1 \le e \le 10^6$
• $a \ne b$
• All shady suburbs will be a valid value within the range of $v$.

Example 1

8 7
2 4
3
0 1 5
0 1
0 2
2 5
4 5
2 6
6 7
4 7

3

Example 2

3 2
0 2
1
1
0 1
1 2

-1

Python Template

v, e = map(int, input().split())
a, b = map(int, input().split(" "))
s = int(input())
blocked = list(map(int, input().split(" ")))
roads = [tuple(map(int, input().split(" "))) for _ in range(e)]

# print(...)