#include <bits/stdc++.h>
using namespace std;
auto sol = [](int n, int m, int k, auto adj) {
vector c(n + 1, 0);
vector s(0, 0);
int c0 = n;
int c2 = 0;
auto rec = [&](const auto& self, int cur) -> void {
c[cur] = 1;
s.push_back(cur);
c0--;
if (c0 == c2) return;
for (int nxt : adj[cur]) {
if (c[nxt] != 0) continue;
self(self, nxt);
if (c0 == c2) return;
}
c[cur] = 2;
s.pop_back();
c2++;
};
for (int i = 1; i <= n; i++) {
if (c[i] != 0) continue;
rec(rec, i);
if (c0 == c2) break;
}
if (s.size() >= n - 2 * k + 2) {
s.resize(n - 2 * k + 2);
return pair(1, s);
}
else {
vector ret(0, 0);
for (int i = 1; i <= n; i++) {
if (c[i] != 0) continue;
ret.push_back(i);
if (ret.size() == k) break;
}
assert(ret.size() == k);
for (int i = 1; i <= n; i++) {
if (c[i] != 2) continue;
ret.push_back(i);
if (ret.size() == 2 * k) break;
}
assert(ret.size() == 2 * k);
return pair(2, ret);
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m, k; cin >> n >> m >> k;
vector adj(n + 1, vector(0, 0));
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
auto [type, res] = sol(n, m, k, adj);
if (type == 1) {
cout << 1 << '\n';
for (int i = 0; i < n - 2 * k + 2; i++) cout << res[i] << ' ';
cout << '\n';
}
else {
cout << 2 << '\n';
for (int i = 0; i < k; i++) cout << res[i] << ' ';
cout << '\n';
for (int i = k; i < 2 * k; i++) cout << res[i] << ' ';
cout << '\n';
}
}
