题目描述

有$N$种珠宝，编号为$1、2、\dots、N$，有$M$个限制条件，第$i$个条件为$A_i$和$B_i$。表示$A_i$和$B_i$可以相邻。

现在你要挑选出一些珠宝拼成一排作为礼物送给Alice，但$Alice$ 对一些种类的珠宝特别喜欢，所以要求必须包含$K$ 种珠宝。

给出必须选择的珠宝，请你求解，让Alice开心的最小珠宝长度。如果无法选出来，输出-1

约束条件

所有输入值都是整数。

$1 ≤ N ≤ 10^5$

$0 ≤ M ≤ 10^5$

$1 ≤ A_i < B_i ≤ N$

$如果 i ≠ j, (A_i, B_i) ≠ (A_j, B_j).$

$1 ≤ K ≤ 17$

$1 ≤ C_1 < C_2 < \dots < C_K ≤ N$

输入

第一行两个整数 $N,M$

接下来$M$行，表示一个限制条件

接下来一行一个整数 $K$, 表示必须要选出来的珠宝的种类数

最后一行 $K$ 个整数，$C_1,C_2,...C_K$ 表示必须选择的珠宝

输出

选出来的珠宝的最小长度

样例输入 1

4 3
1 4
2 4
3 4
3
1 2 3

样例输出 1

5

珠宝的序列为$[1,4,2,4,3]$, 包含珠宝$1,2,3$.

样例输入 2

4 3
1 4
2 4
1 2
3
1 2 3

样例输出 2

-1

样例输入 3

10 10
3 9
3 8
8 10
2 10
5 8
6 8
5 7
6 7
1 6
2 4
4
1 2 7 9

样例输出 3

11

珠宝的序列为$[1,6,7,5,8,3,9,3,8,10,2]$, 包含珠宝$1,2,7,9$.