#P11811. [PA 2015] 人赢 / Mistrzostwa
[PA 2015] 人赢 / Mistrzostwa
题目背景
译自 PA 2015 R2.
题目描述
给定一张 个点 条边的简单(无重边自环的)无向图 。其中节点编号 。
给定正整数 。选出一个最大的点集 ,满足:
- ,。换句话说, 向 内点至少连了 条边。
- 的导出子图(induced subgraph)是连通的。
你需要构造一个 使得 取到最大值,或者报告无解。
点集 的导出子图定义为 ,其中 。
输入格式
第一行,三个正整数 。
接下来 行,每行两个正整数 ,表示 。
输出格式
如果符合条件的 不存在,输出一行一个 。
否则,第一行输出 ,第二行升序输出 中节点的编号。
4 4 2
1 2
2 3
3 4
4 2
3
2 3 4
3 2 2
1 2
2 3
NIE
提示
- ;
- 。
- 给定的图无重边自环。