You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC190E] Magical Ornament

题面翻译

AtCoder 王国流通着 $N$ 种魔法石，编号为 $1,2,\dots,N$。高桥想要把魔法石排成一列做成装饰品。

有的魔法石能够相邻放在一起，有的魔法石却不行。有 $M$ 组魔法石是可以相邻的，分别是 $($魔法石 $A_1,$ 魔法石 $B_1),\ ($魔法石 $A_2,$ 魔法石 $B_2),\ \dots,\ ($魔法石 $A_M,$ 魔法石 $B_M)$。除此之外的任何两个魔法石都不能相邻摆放。（可以相邻的魔法石摆放前后顺序不限。）

请判断是否存在这样一种排列方式，使得其中包含 $C_1,C_2,\dots,C_K$ 中的每一种魔法石。如果存在，求形成这样一个序列所需的最小宝石数量。如果不存在，输出 -1。

输入格式

输入格式如下。第一行两个整数$N,M$，接下来$M$行每行两个整数$A_i,B_i$，后面一行一个整数$K$，再后面$K$行每行一个整数$C_i$。

$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$

输出格式

一个整数表示答案。如果不存在这样的摆法输出-1。

样例 #1

样例输入 #1

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

样例输出 #1

5

样例 #2

样例输入 #2

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

样例输出 #2

-1

样例 #3

样例输入 #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\ <\ = 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$