#include <bits/stdc++.h>
using namespace std;
set<pair<int, int> > s;
vector<int> v[100005];
bool del[100005];
int deg[100005], occ[100005];
void remove(int node) {
  if (del[node]) return;
  s.erase({deg[node], node});
  del[node] = 1;
  for (int u : v[node]) {
    if (!del[u]) {
      s.erase({deg[u], u});
      deg[u]--;
      s.insert({deg[u], u});
    }
  }
}
int main() {
  int n, m, sq = 1;
  scanf("%d%d", &n, &m);
  while (sq * sq < n) sq++;
  while (m--) {
    int a, b;
    scanf("%d%d", &a, &b);
    v[a].push_back(b);
    v[b].push_back(a);
    deg[a]++;
    deg[b]++;
  }
  for (int i = 1; i <= n; i++) s.insert({deg[i], i});
  vector<int> ans;
  int sum = 0;
  while (!s.empty()) {
    auto p = *s.begin();
    s.erase(s.begin());
    sum += p.first;
    if (p.first + 1 >= sq) {
      printf("2\n");
      vector<int> d({p.second});
      occ[p.second] = 1;
      while (1) {
        pair<int, int> nex(1e9, 0);
        for (int u : v[d.back()]) {
          if (!del[u]) nex = min(nex, make_pair(occ[u], u));
        }
        if (nex.first) {
          printf("%d\n", (int)d.size() - nex.first + 1);
          for (int i = nex.first - 1; i < d.size(); i++) printf("%d ", d[i]);
          return 0;
        }
        d.push_back(nex.second);
        occ[nex.second] = d.size();
      }
    }
    ans.push_back(p.second);
    remove(p.second);
    for (int u : v[p.second]) remove(u);
  }
  assert(sum < n);
  printf("1\n");
  for (int i = 0; i < sq; i++) printf("%d ", ans[i]);
}
