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.

问题描述

有 $n$ 种石头，种类的编号为1~ $n$。

小A想将石头排成一排， 组成一个魔法阵。

只有 $m$ 组石头可以放在相邻的位置，分别是 $(a_1,b_1), (a_2,b_2),...,(a_m,b_m)$，其余种类的石头不可以放在相邻的位置。

请判断是否存在这样一种排列方式，使得其中包含 $c_1, c_2, ..., c_k$ 中的每一种石头。

如果存在，输出最少需要的石头的数量；否则输出-1.

输入格式

第一行两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行两个数，表示 $a_i$ 和 $b_i$。

接下来一行一个整数 $k$。

接下来一行 $k$ 个整数 $c_1, c_2, \dots , c_k$。

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

5

解释1

1 4 2 4 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

11

解释2

2 10 8 3 9 3 8 5 7 6 1 为一种合法的方案

数据范围

$n \le 10^5; 0\le m\le 10^5; 1\le a_i\lt b_i \le n; 1\le k\le 17$

$1 \le c_1 \lt c_1 \dots \lt c_k \le n$

保证 $i \neq j$ 时有 $(a_i,b_i) \neq (a_j,b_j)$