#include <bits/stdc++.h>
using namespace std;
int n, m, k, vis[100009], go[100009];
vector<int> v[100009], vv, v2[2];
void solve() {
  if (vv.size() <= k) {
    cout << "2\n" << vv.size() << "\n";
    for (auto i : vv) cout << i << " ";
    exit(0);
  }
  memset(vis, 0, sizeof vis);
  int sz = vv.size();
  for (int i = 0; i < sz; i++) {
    vis[vv[i]] = i + 1;
    for (auto j : v[vv[i]])
      if (vis[j] && j != vv[(i - 1 + sz) % sz] && j != vv[(i + 1) % sz]) {
        if (i + 1 - vis[j] + 1 > sz / 2)
          vv.erase(vv.begin() + vis[j], vv.begin() + i);
        else {
          vv.erase(vv.begin() + i + 1, vv.end());
          vv.erase(vv.begin(), vv.begin() + vis[j] - 1);
        }
        solve();
        return;
      }
  }
  cout << "1\n";
  k = (k + 1) / 2;
  while (k--) {
    cout << vv.back() << " ";
    vv.pop_back();
    vv.pop_back();
  }
  exit(0);
}
void dfs(int node, int p) {
  if (vis[node]) {
    while (p != node) vv.push_back(p), p = go[p];
    vv.push_back(node);
    solve();
  }
  vis[node]++;
  for (auto i : v[node])
    if (i != p) {
      go[i] = node;
      dfs(i, node);
    }
}
void solve2(int node, int p, int col) {
  v2[col].push_back(node);
  for (auto i : v[node])
    if (i != p) solve2(i, node, 1 - col);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    v[x].push_back(y), v[y].push_back(x);
  }
  dfs(1, 0);
  solve2(1, 0, 0);
  if (v2[1].size() > v2[0].size()) v2[0] = v2[1];
  cout << "1\n";
  for (int i = 1; i <= (k + 1) / 2; i++) cout << v2[0][i - 1] << " ";
}
