#include <bits/stdc++.h>
using namespace std;
const long long INF = 2e9;
const long long MB = 20;
const long long MOD = 998244353;
const long long maxN = 1e7 + 1;
vector<vector<long long>> g;
vector<bool> used;
vector<long long> h, pr;
long long n, m, k, q = -1, st = -1;
void dfs(long long v) {
  used[v] = true;
  for (long long u : g[v]) {
    if (!used[u]) {
      h[u] = h[v] + 1;
      pr[u] = v;
      dfs(u);
    } else if (h[v] - h[u] < k && h[v] - h[u] > 1) {
      q = v;
      st = u;
    }
  }
}
vector<long long> c;
void dfs1(long long v) {
  used[v] = true;
  for (long long u : g[v]) {
    if (!used[u] && h[u] < k) {
      c[u] = c[v] ? 0 : 1;
      dfs1(u);
    }
  }
}
void solve() {
  cin >> n >> m >> k;
  g.resize(n);
  for (long long i = 0; i < m; i++) {
    long long from, to;
    cin >> from >> to;
    from--;
    to--;
    g[from].push_back(to);
    g[to].push_back(from);
  }
  used.resize(n);
  pr.resize(n);
  h.resize(n);
  dfs(0);
  if (q != -1) {
    vector<long long> ans = {q};
    while (q != st) {
      q = pr[q];
      ans.push_back(q);
    }
    cout << "2\n" << ans.size() << "\n";
    for (long long i : ans) cout << i + 1 << " ";
    return;
  }
  c.resize(n, -1);
  fill(used.begin(), used.end(), false);
  c[0] = 0;
  dfs1(0);
  vector<long long> ans;
  long long cnt1 = 0, cnt2 = 0;
  for (long long i = 0; i < n; i++) {
    if (c[i] == 0)
      cnt1++;
    else if (c[i] == 1)
      cnt2++;
  }
  if (cnt1 > cnt2) {
    for (long long i = 0; i < n; i++) {
      if (c[i] == 0) ans.push_back(i);
    }
  } else {
    for (long long i = 0; i < n; i++) {
      if (c[i] == 1) ans.push_back(i);
    }
  }
  cout << "1\n";
  for (long long i = 0; i < (k + 1) / 2; i++) cout << ans[i] + 1 << " ";
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout << fixed;
  cout.precision(12);
  srand(time(0));
  long long t = 1;
  while (t--) solve();
}
