#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int n, m, ROOT, head;
bool vis[MAXN];
int depth[MAXN], deg[MAXN];
vector<int> adj[MAXN];
vector<int> c;
stack<int> stk;
pair<bool, vector<int> > independentSet() {
  set<pair<int, int> > s;
  vector<int> v;
  for (auto i = 0; i < (n); i++) s.insert(make_pair(deg[i], i));
  while (!s.empty()) {
    int node = s.begin()->second;
    s.erase(s.begin());
    if (vis[node]) continue;
    v.push_back(node);
    vis[node] = true;
    for (auto u : adj[node]) {
      if (vis[u]) continue;
      vis[u] = true;
      for (auto v : adj[u]) {
        if (v == u) continue;
        --deg[v];
        s.insert(make_pair(deg[v], v));
      }
    }
  }
  if (v.size() >= ROOT)
    return make_pair(true, v);
  else
    return make_pair(false, vector<int>{});
}
void simpleCycle() {
  while (!stk.empty() && stk.top() != head) {
    c.push_back(stk.top());
    stk.pop();
  }
  c.push_back(head);
  reverse(c.begin(), c.end());
  cout << "2\n" << c.size() << "\n";
  for (auto u : c) cout << u + 1 << " ";
  exit(0);
}
void dfs(int node, int d) {
  if (depth[node] > 0) {
    if (d - depth[node] == ROOT) {
      head = node;
      simpleCycle();
    }
    return;
  }
  depth[node] = d;
  stk.push(node);
  for (auto u : adj[node]) {
    dfs(u, d + 1);
  }
  stk.pop();
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m;
  for (auto i = 0; i < (m); i++) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
    ++deg[u];
    ++deg[v];
  }
  ROOT = (int)sqrt(n);
  if (ROOT * ROOT < n) ++ROOT;
  auto is = independentSet();
  if (is.first) {
    cout << "1\n";
    for (auto i = 0; i < (ROOT); i++) cout << is.second[i] + 1 << " ";
    exit(0);
  } else {
    dfs(0, 1);
  }
}
