CF1364D Ehab's Last Corollary
题目描述
给出一张 $n$ 个点的无向连通图和一个常数 $k$。
你需要解决以下两个问题的任何一个：
1. 找出一个大小为 $\lceil\frac k2\rceil$ 的独立集。
2. 找出一个大小不超过 $k$ 的环。
独立集是一个点的集合，满足其中任意两点之间在原图上没有边直接相连。
可以证明这两个问题必然有一个可以被解决。
输入格式
第一行三个整数 $n, m, k$。
之后 $m$ 行，每行两个整数 $u, v$，表示在图上有一条 $u, v$ 之间的双向边。
保证 $3\le k\le n\le10^5$，$n-1\le m\le2\times10^5$，$1\le u,v\le n$。
输出格式
第一行输出你解决的问题编号，即 `1` 或 `2`。
若你解决的是问题 1，则第二行需要输出 $\lceil\frac k2\rceil$ 个整数，表示你找到的独立集中点的编号。
否则你需要在第二行输出一个整数 $c$，表示你找到的环的大小，之后第三行输出 $c$ 个整数表示环上的点，你需要保证这 $c$ 个点中相邻的点之间有边。
说明/提示
In the first sample:
Notice that printing the independent set $ \{2,4\} $ is also OK, but printing the cycle $ 1-2-3-4 $ isn't, because its length must be at most $ 3 $ .
In the second sample:
Notice that printing the independent set $ \{1,3\} $ or printing the cycle $ 2-1-4 $ is also OK.
In the third sample:
In the fourth sample:
