选石头
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
问题描述
有 种石头,种类的编号为1~ 。
小A想将石头排成一排, 组成一个魔法阵。
只有 组石头可以放在相邻的位置,分别是 ,其余种类的石头不可以放在相邻的位置。
请判断是否存在这样一种排列方式,使得其中包含 中的每一种石头。
如果存在,输出最少需要的石头的数量;否则输出-1.
输入格式
第一行两个整数 和 。
接下来 行,每行两个数,表示 和 。
接下来一行一个整数 。
接下来一行 个整数 。
4 3
1 4
2 4
3 4
3
1 2 3
5
解释1
1 4 2 4 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
11
解释2
2 10 8 3 9 3 8 5 7 6 1 为一种合法的方案
数据范围
$n \le 10^5; 0\le m\le 10^5; 1\le a_i\lt b_i \le n; 1\le k\le 17$
保证 时有
暑期模拟赛 一
- Status
- Done
- Rule
- IOI
- Problem
- 5
- Start at
- 2024-7-11 8:30
- End at
- 2024-7-11 12:00
- Duration
- 3.5 hour(s)
- Host
- Partic.
- 9