#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int n, m, t1, t2, t3, lim;
int dep[N], vis[N], fg[N];
vector<int> g[N];
vector<int> sta;
void dfs1(int p) {
  sta.push_back(p);
  vis[p] = 1;
  for (int q : g[p]) {
    if (!vis[q]) {
      dep[q] = dep[p] + 1;
      dfs1(q);
    } else {
      if (dep[q] && dep[p] - dep[q] >= lim - 1) {
        cout << 2 << endl << dep[p] - dep[q] + 1 << endl;
        while (sta.back() != q && sta.size()) {
          cout << sta.back() << " ";
          sta.pop_back();
        }
        cout << q << endl;
        exit(0);
      }
    }
  }
  sta.pop_back();
}
void dfs2(int p) {
  vis[p] = 1;
  for (int q : g[p])
    if (!vis[q]) dfs2(q);
  for (int q : g[p])
    if (!fg[p]) fg[q] = 1;
}
signed main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  lim = 1;
  while (lim * lim < n) ++lim;
  for (int i = 1; i <= m; i++) {
    cin >> t1 >> t2;
    g[t1].push_back(t2);
    g[t2].push_back(t1);
  }
  dep[1] = 1;
  dfs1(1);
  memset(vis, 0, sizeof vis);
  dfs2(1);
  int cnt = lim;
  cout << 1 << endl;
  for (int i = 1; i <= n && cnt; i++) {
    if (!fg[i]) cout << i << " ", --cnt;
  }
}
