Magical Ornament

题目描述

AtCoder 王国中分布着 $N$ 种魔法宝石，编号为 $1, 2, \ldots, N$。
Takahashi 正在尝试通过将宝石排成一行来制作饰品。
对于某些宝石对，我们可以将这两种宝石放在相邻位置；对于其他宝石对，则不可以。我们有 $M$ 对可以相邻的宝石：$(\text{宝石 }A_1, \text{宝石 }B_1)$、$(\text{宝石 }A_2, \text{宝石 }B_2)$、$\ldots$、$(\text{宝石 }A_M, \text{宝石 }B_M)$。对于其它宝石对，这两种宝石不能相邻。（这些对的顺序不影响。）
判定是否可以形成一个序列，使得该序列中包含每种类型 $C_1, C_2, \dots, C_K$ 的一个或多个宝石。如果可能，找到形成这样一个序列所需的最少宝石数。

输入格式

输入从标准输入按以下格式提供： $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$

输出格式

输出形成一个包含每种类型 $C_1, C_2, \dots, C_K$ 的一个或多个宝石的序列所需的最少宝石数。
如果无法形成这样的序列，输出 $-1$。

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

5

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

-1

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

提示

输入中的所有值均为整数。 $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例如，通过按顺序排列宝石 $[1, 4, 2, 4, 3]$，我们可以形成一个长度为 $5$ 且包含宝石 $1, 2, 3$ 的序列。
例如，通过按顺序排列宝石 $[1, 6, 7, 5, 8, 3, 9, 3, 8, 10, 2]$，我们可以形成一个长度为 $11$ 且包含宝石 $1, 2, 7, 9$ 的序列。

标签: AtCoder|abc190E

来源

AtCoder|abc190E