#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
long double PI = acosl(-1);
const long long infl = 3e18 + 100;
const int inf = 1e8 + 100;
const int nmax = 1e5 + 5;
const int MAXLG = log2(nmax) + 1;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n, rutn;
int par[nmax], level[nmax];
vector<int> g[nmax];
void dfs(int u, int p = 0) {
  par[u] = p, level[u] = level[p] + 1;
  for (int v : g[u])
    if (v != p) {
      if (level[v]) {
        int d = -level[v] + level[u] + 1;
        if (d >= rutn) {
          cout << "2\n";
          cout << d << "\n";
          while (u != par[v]) cout << u << " ", u = par[u];
          exit(0);
        }
      } else
        dfs(v, u);
    }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int m;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  rutn = sqrt(n);
  if (rutn * rutn != n) rutn++;
  dfs(1);
  while (true) {
    priority_queue<pair<pair<int, int>, int> > pq;
    vector<int> deg(n + 1);
    for (int i = 1; i <= n; i++) {
      pq.push({{-g[i].size(), rng()}, i});
      deg[i] = g[i].size();
    }
    vector<int> ans;
    vector<bool> vis(n + 1);
    while (pq.size()) {
      auto z = pq.top();
      pq.pop();
      int u = z.second;
      if (vis[u]) continue;
      ans.push_back(u);
      vis[u] = true;
      for (int v : g[u]) {
        if (!vis[v]) {
          for (int v1 : g[v]) {
            deg[v1]--;
            pq.push({{-deg[v1], rng()}, v1});
          }
        }
        vis[v] = true;
      }
      if (ans.size() >= rutn) {
        cout << "1\n";
        for (int x : ans) cout << x << " ";
        exit(0);
      }
    }
  }
}
