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 \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 翻译