← 返回题目列表

Codeforces · 1325/F

F. Ehab 最后定理

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

今年是 5555 年。你有一个图,你想找到一个长周期和一个巨大的独立集,因为你可以。但现在,我们还是继续寻找其中一个吧。

给定一个具有 $$$n$$$ 个顶点的连通图,您可以选择:

- 找到一个恰好具有 $$$\lceil\sqrt{n}\rceil$$$ 个顶点的独立集。
- 找到一个长度至少为 $$$\lceil\sqrt{n}\rceil$$$ 的简单循环。

独立集是一组顶点,其中没有两个顶点通过边连接。简单循环是不两次包含任何顶点的循环。我有证据证明你总能解决其中一个问题,但它太长了,无法适应这个边距。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$5 \le n \le 10^5$$$, $$$n-1 \le m \le 2 \cdot 10^5$$$) - 图中顶点和边的数量。

接下来的 $$$m$$$ 行包含两个以空格分隔的整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$),这意味着顶点 $$$u$$$ 和 $$$v$$$ 之间有一条边。保证图是连通的并且不包含任何自环或重边。

输出

如果您选择解决第一个问题,则在第一行打印“1”,后跟一行包含 $$$\lceil\sqrt{n}\rceil$$$ 不超过 $$$n$$$ 的不同整数,即所需独立集中的顶点。

但是,如果您选择解决第二个问题,则在第一行打印“2”,后跟一行包含一个整数 $$$c$$$,表示找到的循环的长度,后跟一行包含 $$$c$$$ 不同的整数,不超过 $$$n$$$ 的整数,即所需循环中的顶点,按照它们在循环中出现的顺序排列。

示例

输入 #1

6 6
1 3
3 4
4 2
2 6
5 6
5 1

输出 #1

1
1 6 4

输入 #2

6 8
1 3
3 4
4 2
2 6
5 6
5 1
1 4
2 5

输出 #2

2
4
1 5 2 4

输入 #3

5 4
1 2
1 3
2 4
2 5

输出 #3

1
3 4 5

注意

在第一个示例中:

请注意,您可以解决任一问题,因此打印循环 $$$2-4-3-1-5-6$$$ 也是可以接受的。

在第二个示例中:

请注意,如果有多个答案,您可以打印任何答案,因此打印周期 $$$2-5-6$$$ 是可以接受的。

在第三个示例中: