#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m;
  cin >> n >> m;
  int sq = ceil(sqrt(n));
  vector<vector<int>> adj(n);
  for (int i = 0, u, v; i < m; ++i) {
    cin >> u >> v;
    adj[--u].push_back(--v);
    adj[v].push_back(u);
  }
  vector<int> dep(n, -1);
  vector<int> path;
  function<void(int, int, int)> dfs = [&](int id, int fa, int depth) {
    path.push_back(id);
    dep[id] = depth;
    for (auto e : adj[id]) {
      if (e == fa) continue;
      if (dep[e] == -1) {
        dfs(e, id, depth + 1);
        continue;
      }
      if (dep[id] - dep[e] + 1 >= sq) {
        cout << 2 << '\n';
        cout << dep[id] - dep[e] + 1 << '\n';
        while (true) {
          cout << path.back() + 1 << ' ';
          if (path.back() == e) break;
          path.pop_back();
        }
        exit(0);
      }
    }
    path.pop_back();
  };
  dfs(0, -1, 0);
  vector<int> cnt(sq);
  for (auto e : dep) cnt[e % (sq - 1)]++;
  int maxn = *max_element(cnt.begin(), cnt.end());
  cout << 1 << '\n';
  vector<int> ans;
  for (int i = 0; i < n; ++i) {
    if (cnt[dep[i] % (sq - 1)] == maxn) ans.push_back(i);
  }
  for (int i = 0; i < sq; ++i) cout << ans[i] + 1 << ' ';
  return 0;
}
