← 返回题目列表

AtCoder · abc190_e

E. 魔法饰品

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 各种神奇宝石,编号 1, 2, \ldots, N,分布在AtCoder王国。
高桥正在尝试通过将宝石排成一排来制作装饰品。
对于某些宝石对,我们可以将两颗宝石并排放置;对于其他对,我们不能。我们有 M 两颗宝石可以相邻的对:(宝石 A_1, 宝石 B_1), (宝石 A_2, 宝石 B_2), \ldots,(宝石 A_M, 宝石 B_M)。对于其他对,两颗宝石不能相邻。 (这些对中的顺序并不重要。)
确定是否可以形成包含每种类型的一颗或多颗宝石的宝石序列 C_1, C_2, \dots, C_K。如果答案是肯定的,请找出形成这样一个序列所需的最少石头数量。

约束

  • 输入中的所有值都是整数。
  • 1 ≤ N ≤ 10^5
  • 0 ≤ M ≤ 10^5
  • 1 ≤ A_i < B_i ≤ N
  • If i ≠ j, (A_i, B_i) ≠ (A_j, B_j).
  • 1 ≤ K ≤ 17
  • 1 ≤ C_1 < C_2 < \dots < C_K ≤ N

输入

输入由标准输入按以下格式给出:

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 代替。


示例输入 1

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

示例输出 1

5

例如,按顺序排列宝石 [1, 4, 2, 4, 3],我们可以形成一个长度的序列 5 与宝石 1, 2, 3.


示例输入 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

例如,按顺序排列宝石 [1, 6, 7, 5, 8, 3, 9, 3, 8, 10, 2],我们可以形成一个长度的序列 11 与宝石 1, 2, 7, 9.