← 返回题目
题库练习 魔法饰品
← 上一题 下一题 →

A5169 | 魔法饰品

时间限制2s
内存限制1024MB
通过 / 提交0/0

题目描述

在遥远的王国中，流通着编号为 $1, 2, \dots, N$ 的 $N$ 种魔法石。
NoonMaple打算将魔法石排成一列来制作装饰品。
魔法石之间有些可以相邻，有些则不行。可以相邻的魔法石对有 $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
4 3
1 4
2 4
3 4
3
1 2 3
输出 #1
5
输入 #2
4 3
1 4
2 4
1 2
3
1 2 3
输出 #2
-1
输入 #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
C++ 编辑器
输入
输出