#include <bits/stdc++.h>
using namespace std;
int d[100100], n, m, k, f, f1, pos[100100], ff;
vector<int> li;
vector<vector<int> > g(100100);
void dfs(int ver, int p) {
  if (ff == 1) {
    return;
  }
  li.push_back(ver);
  d[ver] = li.size();
  for (auto to : g[ver]) {
    if (to == ver) {
      continue;
    }
    if (d[to] == 0) {
      dfs(to, ver);
    } else {
      if (d[ver] - d[to] + 1 >= k && ff == 0) {
        cout << 2 << "\n" << d[ver] - d[to] + 1 << '\n';
        for (int i = d[to] - 1; i < d[ver]; i++) {
          cout << li[i] << " ";
        }
        ff = 1;
        return;
      }
    }
  }
  if (!pos[ver]) {
    for (auto to : g[ver]) {
      pos[to] = 1;
    }
  }
  li.pop_back();
}
int main() {
  cin >> n >> m;
  k = 1;
  while (k * k < n) {
    k++;
  }
  for (int i = 1; i <= m; i++) {
    cin >> f >> f1;
    g[f].push_back(f1);
    g[f1].push_back(f);
  }
  dfs(1, -1);
  if (ff == 1) {
    return 0;
  }
  cout << 1 << '\n';
  for (int i = 1; k != 0; i++) {
    if (pos[i] == 0) {
      cout << i << " ";
      k--;
    }
  }
}
