给定一个具有 $$$n$$$ 个顶点和一个整数 $$$k$$$ 的连通无向图,您必须:
- 找到一个恰好具有 $$$\lceil\frac{k}{2}\rceil$$$ 个顶点的独立集。
- 或者找到一个长度至多 $$$k$$$ 的简单循环。
独立集是一组顶点,其中没有两个顶点通过边连接。简单循环是不两次包含任何顶点的循环。
我有一个证明,对于任何输入,你总是可以解决至少一个这些问题,但它留给读者作为练习。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$3 \le k \le n \le 10^5$$$, $$$n-1 \le m \le 2 \cdot 10^5$$$) — 图中的顶点和边的数量,参数 $$$k$$$ 来自声明。
接下来的 $$$m$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$),这意味着顶点 $$$u$$$ 和 $$$v$$$ 之间有一条边。保证图是连通的并且不包含任何自环或重边。
输出
如果您选择解决第一个问题,则在第一行打印 $$$1$$$,后跟一行包含 $$$\lceil\frac{k}{2}\rceil$$$ 不超过 $$$n$$$ 的不同整数,即所需独立集中的顶点。
但是,如果您选择解决第二个问题,则在第一行打印 $$$2$$$,后跟一行包含一个整数 $$$c$$$,表示找到的循环的长度,后跟一行包含 $$$c$$$ 不超过 $$$n$$$ 的不同整数,即所需循环中的顶点,按照它们在循环中出现的顺序排列。
示例
输入 #1
4 4 3 1 2 2 3 3 4 4 1
输出 #1
1 1 3
输入 #2
4 5 3 1 2 2 3 3 4 4 1 2 4
输出 #2
2 3 2 3 4
输入 #3
4 6 3 1 2 2 3 3 4 4 1 1 3 2 4
输出 #3
2 3 1 2 3
输入#4
5 4 5 1 2 1 3 2 4 2 5
输出#4
1 1 4 5
注意
在第一个示例中:
请注意,打印独立集 $$$\{2,4\}$$$ 也可以,但打印循环 $$$1-2-3-4$$$ 不行,因为它的长度最多必须为 $$$3$$$。
在第二个示例中:
注意,打印独立集 $$$\{1,3\}$$$ 或打印循环 $$$2-1-4$$$ 也可以。
在第三个示例中:
在第四个示例中: