← 返回题目列表

Codeforces · 1364/D

D. Ehab 的最后推论

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

给定一个具有 $$$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$$$ 也可以。

在第三个示例中:

在第四个示例中: