#include <bits/stdc++.h>
using namespace std;
int n, m, r, start;
bool ok;
vector<int> g[(int)(1e5 + 4)], sol, leaf;
bitset<(int)(1e5 + 4)> used;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void dfs(int node) {
  if (sol.size() == r) return;
  used[node] = 1;
  sol.emplace_back(node);
  for (auto to : g[node]) used[to] = 1;
  for (auto to : g[node]) {
    for (auto it : g[to])
      if (!used[it]) dfs(it);
  }
}
void dfs2(int node, int father) {
  if (ok) return;
  used[node] = 1;
  sol.emplace_back(node);
  for (auto to : g[node]) {
    if (!used[to])
      dfs2(to, node);
    else if (to != father && to == start) {
      if (sol.size() >= r) {
        ok = 1;
        return;
      }
    }
  }
  if (!ok) sol.pop_back();
}
int main() {
  cin >> n >> m;
  r = ceil(sqrt(n));
  for (int i = 0, x, y; i < m; ++i) {
    cin >> x >> y;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
  }
  dfs(1);
  int cnt = 30, node;
  while (cnt && sol.size() != r) {
    sol.clear();
    used.reset();
    node = rng() % n + 1;
    dfs(node);
    --cnt;
  }
  if (sol.size() == r) {
    cout << "1\n";
    for (auto it : sol) cout << it << ' ';
    return 0;
  }
  while (!ok) {
    used.reset();
    sol.clear();
    node = rng() % n + 1;
    start = node;
    dfs2(node, 0);
  }
  cout << "2\n" << sol.size() << '\n';
  for (auto it : sol) cout << it << ' ';
  return 0;
}
