Problem Statement

There are $N$ kinds of magical gems, numbered $1, 2, \ldots, N$, distributed in the AtCoder Kingdom. Takahashi is trying to make an ornament by arranging gems in a row. For some pairs of gems, we can put the two gems next to each other; for other pairs, we cannot. We have $M$ pairs for which the two gems can be adjacent: (Gem $A_1$, Gem $B_1$), (Gem $A_2$, Gem $B_2$), $\ldots$, (Gem $A_M$, Gem $B_M$). For the other pairs, the two gems cannot be adjacent. (Order does not matter in these pairs.) Determine whether it is possible to form a sequence of gems that has one or more gems of each of the kinds $C_1, C_2, \dots, C_K$. If the answer is yes, find the minimum number of stones needed to form such a sequence.

Constraints

• All values in input are integers.
• $1 ≤ N ≤ 10^5$
• $0 ≤ M ≤ 10^5$
• $1 ≤ A_i < B_i ≤ N$
• If $i ≠ j$, $(A_i, B_i) ≠ (A_j, B_j)$.
• $1 ≤ K ≤ 17$
• $1 ≤ C_1 < C_2 < \dots < C_K ≤ N$

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\hspace{7mm}\vdots
A_M B_M
K
C_1 C_2 \cdots C_K

Output

Print the minimum number of stones needed to form a sequence of gems that has one or more gems of each of the kinds $C_1, C_2, \dots, C_K$. If such a sequence cannot be formed, print -1 instead.