今年是 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$$$ 是可以接受的。
在第三个示例中: