AT_abc190_e [ABC190E] Magical Ornament

题目描述

在 AtCoder 王国中，流通着编号为 $1, 2, \dots, N$ 的 $N$ 种魔法石。
高桥君打算将魔法石排成一列来制作装饰品。
魔法石之间有些可以相邻，有些则不行。可以相邻的魔法石对有 $M$ 组，分别为 $(A_1, B_1), (A_2, B_2), \dots, (A_M, B_M)$，除此之外的组合都不能相邻（这些组合中，石头的顺序无关紧要）。
请判断是否可以制作一个包含魔法石 $C_1, C_2, \dots, C_K$，且每种至少出现一次的魔法石序列。如果可以，请求出制作这样一个序列所需的最少魔法石数量。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$
$K$
$C_1$ $C_2$ $\cdots$ $C_K$

输出格式

输出制作包含魔法石 $C_1, C_2, \dots, 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 \leq N \leq 10^5$
• $0 \leq M \leq 10^5$
• $1 \leq A_i < B_i \leq N$
• 若 $i \neq j$，则 $(A_i, B_i) \neq (A_j, B_j)$
• $1 \leq K \leq 17$
• $1 \leq C_1 < C_2 < \dots < C_K \leq N$

样例解释 1

例如，将魔法石排列为 $[1, 4, 2, 4, 3]$，可以制作一个包含魔法石 $1, 2, 3$ 的长度为 $5$ 的序列。

样例解释 3

例如，将魔法石排列为 $[1, 6, 7, 5, 8, 3, 9, 3, 8, 10, 2]$，可以制作一个包含魔法石 $1, 2, 7, 9$ 的长度为 $11$ 的序列。

由 ChatGPT 4.1 翻译