简单题。
特判掉 \(m = n - 1\) 的情况，此时一定能找到一个大小为 \(\left\lceil\frac{k}{2}\right\rceil\) 的独立集，二分图染色即可。
否则，我们建出 dfs tree，找到一条连接的两个端点深度之差最小的返祖边，设它为 \((u, v)\)，且 \(dep_u > dep_v\)。
若环长 \(c = dep_u - dep_v + 1 \le k\) 就完成任务了，否则 \(c > k\)，我们在环上隔一个点取一个点即可。因为这是长度最小的环，所以中间不会再出现返祖边。
code
// Problem: D. Ehab's Last Corollary
// Contest: Codeforces - Codeforces Round 649 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1364/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 100100;
int n, m, K, dep[maxn], fa[maxn], mnd = 1e9, U, V;
bool vis[maxn];
vector<int> G[maxn], vc[2];
void dfs(int u, int f) {
vis[u] = 1;
vc[dep[u] & 1].pb(u);
for (int v : G[u]) {
if (v == f) {
continue;
}
if (vis[v]) {
if (dep[u] > dep[v] && dep[u] - dep[v] + 1 < mnd) {
mnd = dep[u] - dep[v] + 1;
U = u;
V = v;
}
continue;
}
fa[v] = u;
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
void solve() {
scanf("%d%d%d", &n, &m, &K);
for (int _ = 0, u, v; _ < m; ++_) {
scanf("%d%d", &u, &v);
G[u].pb(v);
G[v].pb(u);
}
dfs(1, -1);
if (m == n - 1) {
if (vc[0].size() < vc[1].size()) {
swap(vc[0], vc[1]);
}
puts("1");
for (int i = 0; i < (K + 1) / 2; ++i) {
printf("%d ", vc[0][i]);
}
return;
}
if (mnd <= K) {
printf("2\n%d\n", mnd);
for (int x = U; x != fa[V]; x = fa[x]) {
printf("%d ", x);
}
} else {
puts("1");
int cnt = 0;
for (int x = U, o = 1;; x = fa[x], o ^= 1) {
if (o) {
printf("%d ", x);
if ((++cnt) == (K + 1) / 2) {
break;
}
}
}
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}