问题 E: 最少需要多少机器人
内存限制:1024 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:4
解决:3
题目描述
现在有n种机器人编号是1-n。并且每个机器人都有程序设定。一个程序能让两个机器人互相认识,不会打架。一共有m个程序。现在我们有k个机器人,并且这k个机器人的种类已经给好,无法改变,只能在他们之间加入一些别的机器人来让这一些机器人互相之间不打架。然后每种机器人都有无数个。问最少多少机器人能够满足这K个机器人互相之间不打架。如果无论怎么排都会打架则输出-1
输入
n m (1<=n<=1e5,0<=m<=1e5)
a1 b1
a2 b2
....
am bm
(ai和bi互相认识不会打架)(1<=ai,bi<=n)
k(1<=k<=17)
c1 c2 .....ck
(1<=ci<=n)
a1 b1
a2 b2
....
am bm
(ai和bi互相认识不会打架)(1<=ai,bi<=n)
k(1<=k<=17)
c1 c2 .....ck
(1<=ci<=n)
输出
输出最小的机器人个数或者-1
样例输入 复制
4 3
1 4
2 4
3 4
3
1 2 3
样例输出 复制
5
提示
样例中的5个是1 4 2 4 3,这样1 2 3 都出现了并且这5个机器人不会打架