#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, InfI = INT_MAX, Mod = 998244353;
const long long InfL = LONG_LONG_MAX;
int n, m, sqn;
vector<int> adj[N];
vector<int> ind;
bool vis[N] = {}, indpen[N] = {};
int ent[N], par[N], back_edge[N], back_min[N];
int dfstimer = 0, idma = 1;
void dfs(int x) {
  vis[x] = 1;
  ent[x] = dfstimer++;
  int back_edg = 0, back_mi = x;
  bool pen = 1;
  for (int v : adj[x]) {
    if (!vis[v]) {
      par[v] = x;
      dfs(v);
    } else if (ent[v] < ent[x]) {
      back_edg++;
      back_mi = (ent[v] < ent[back_mi]) ? v : back_mi;
    }
    if (indpen[v]) pen = 0;
  }
  back_edge[x] = back_edg;
  back_min[x] = back_mi;
  idma = (back_edg > back_edge[idma]) ? x : idma;
  if (back_edg < sqn - 1 && pen) {
    ind.push_back(x);
    indpen[x] = 1;
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  sqn = ceil(sqrt(1.0 * n));
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  back_edge[1] = 0;
  dfs(1);
  if (back_edge[idma] >= sqn - 1) {
    cout << 2 << endl;
    vector<int> path;
    int j = idma;
    path.push_back(j);
    while (j != back_min[idma]) {
      j = par[j];
      path.push_back(j);
    }
    cout << path.size() << endl;
    for (int i : path) cout << i << ' ';
    return 0;
  }
  cout << 1 << endl;
  for (int i = 0; i < sqn; i++) cout << ind[i] << ' ';
}
