#include <bits/stdc++.h>
using namespace std;
const short inf = 1 << 14;
const double pi = acos(-1);
const double eps = 1e-9;
const int mod = 1e9 + 7;
const int mf[] = {0, 0, 1, -1}, mc[] = {1, -1, 0, 0};
const int N = 10005;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<int> > g(n);
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<int> l(n), p(n);
  bool ans_cycle = false;
  int may_cycle = 0, start = 0, end = 0, startm = 0, endm = 0;
  function<void(int, int)> dfs = [&](int u, int pad) {
    for (int v : g[u]) {
      if (v == pad) continue;
      if (!l[v]) {
        p[v] = u;
        l[v] = l[u] + 1;
        dfs(v, u);
      } else if (l[u] > l[v]) {
        int t = l[u] - l[v] + 1;
        if (t <= k) {
          ans_cycle = true;
          start = u;
          end = v;
        }
        if (may_cycle < t) {
          may_cycle = t;
          startm = u;
          endm = v;
        }
      }
    }
  };
  l[0] = 1;
  dfs(0, -1);
  if (m == n - 1) {
    vector<int> v0, v1;
    for (int i = 0; i < n; i++)
      if (l[i] & 1)
        v1.push_back(i);
      else
        v0.push_back(i);
    if ((int)v0.size() >= (k + 1) / 2) {
      cout << 1 << '\n';
      for (int i = 0; i < (k + 1) / 2; i++)
        cout << v0[i] + 1 << " \n"[i == (k + 1 / 2) - 1];
    } else {
      cout << 1 << '\n';
      for (int i = 0; i < (k + 1) / 2; i++)
        cout << v1[i] + 1 << " \n"[i == (k + 1 / 2) - 1];
    }
    return 0;
  }
  if (ans_cycle == true) {
    vector<int> ans;
    int u = start;
    while (u != end) {
      ans.push_back(u);
      u = p[u];
    }
    ans.push_back(u);
    cout << 2 << '\n';
    cout << ans.size() << '\n';
    for (auto &i : ans) {
      cout << i + 1 << " \n"[&i == &ans.back()];
    }
    return 0;
  }
  assert(may_cycle > k);
  vector<int> cycle;
  int u = startm;
  while (u != endm) {
    cycle.push_back(u);
    u = p[u];
  }
  cycle.push_back(u);
  vector<int> ans;
  for (int i = 0; i < may_cycle; i += 2) ans.push_back(cycle[i]);
  cout << 1 << '\n';
  for (int i = 0; i < (k + 1) / 2; i++)
    cout << ans[i] + 1 << " \n"[i == (k + 1) / 2 - 1];
  return 0;
}
