#include <bits/stdc++.h>
using namespace std;
// debug /*{{{*/
#define debug(...) __dbg(#__VA_ARGS__, __VA_ARGS__)
template<typename T> concept Container = ranges::range<T> && !convertible_to<T, string_view>;
template<typename T, typename U> ostream& operator<<(ostream& out, const pair<T, U>& v);
template<typename... Args> ostream& operator<<(ostream& out, const tuple<Args...>& v);
template<Container T> ostream& operator<<(ostream& out, const T& v);
template<typename T, typename U>
ostream& operator<<(ostream& out, const pair<T, U>& v) {
out << '(' << v.first << ' ' << v.second << ')';
return out;
}
template<typename... Args>
ostream& operator<<(ostream& out, const tuple<Args...>& v) {
string _;
out << '(';
apply([&](auto&&... x) { (..., (out << _ << x, _ = " ")); }, v);
out << ')';
return out;
}
template<Container T>
ostream& operator<<(ostream& out, const T& v) {
string _;
out << '(';
for (auto i : v) out << _ << i, _ = " ";
out << ')';
return out;
}
template<typename ...Args>
void __dbg(string s, Args&&... x) {
string _;
cerr << '(' << s << ") : ";
(..., (cerr << _ << x, _ = ", "));
cerr << endl;
}
/*}}}*/
using i64 = long long;
auto subtask_1 = [](int n, int m, int k, auto adj) {
vector g(n + 1, vector(n + 1, false));
for (int i = 1; i <= n; i++) {
for (int j : adj[i]) {
g[i][j] = true;
}
}
{
vector p(n - 2 * k + 2, -1);
vector c(n + 1, false);
auto rec = [&](const auto& self, int dep) -> bool {
if (dep == n - 2 * k + 2) {
for (int i = 1; i < n - 2 * k + 2; i++) {
if (g[p[i - 1]][p[i]]) continue;
return false;
}
return true;
}
else {
for (int i = 1; i <= n; i++) {
if (c[i]) continue;
p[dep] = i;
c[i] = true;
if (self(self, dep + 1)) return true;
p[dep] = -1;
c[i] = false;
}
return false;
}
};
if (rec(rec, 0)) {
return pair(1, p);
}
}
{
vector a(0, 0), b(0, 0);
auto rec = [&](const auto& self, int dep) -> bool {
if (dep == n + 1) {
if (a.size() != k) return false;
if (b.size() != k) return false;
for (int i : a) {
for (int j : b) {
if (g[i][j]) return false;
}
}
return true;
}
else {
if (self(self, dep + 1)) return true;
a.push_back(dep);
if (self(self, dep + 1)) return true;
a.pop_back();
b.push_back(dep);
if (self(self, dep + 1)) return true;
b.pop_back();
return false;
}
};
if (rec(rec, 1)) {
vector ret(0, 0);
for (int x : a) ret.push_back(x);
for (int x : b) ret.push_back(x);
return pair(2, ret);
}
}
assert(0);
return pair(-1, vector(0, 0));
};
auto subtask_2 = [](int n, int m, int k, auto adj) {
if (m == i64(n) * (n - 1) / 2) {
vector ret(0, 0);
for (int i = 1; i <= n; i++) ret.push_back(i);
return pair(1, ret);
}
else {
for (int i = 1; i <= n; i++) {
if (adj[i].size() == n - 1) continue;
sort(adj[i].begin(), adj[i].end());
int p = 1;
while (p == i || binary_search(adj[i].begin(), adj[i].end(), p)) p++;
vector ret{ i, p };
return pair(2, ret);
}
assert(0);
return pair(-1, vector(0, 0));
}
};
auto sol = [](int n, int m, int k, auto adj) {
if (n <= 10) return subtask_1(n, m, k, adj);
if (k == 1) return subtask_2(n, m, k, adj);
assert(0);
return pair(-1, vector(0, 0));
};
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';
}
}
