#include <bits/stdc++.h>
using namespace std;
const long long INF = (long long)2e9;
const long long inf = (long long)2e18;
const long double eps = (long double)1e-7;
const long long mod = (long long)1e9 + 7;
const long long MAXN = (long long)1e5 + 1;
const long long MAXC = (long long)2001;
const long long MAXE = (long long)1000;
const long long MAXLOG = 21;
const long long maxlen = (long long)1e5;
const long long asci = (long long)256;
const long long block = 317;
const long double PI = acos(-1);
template <class T>
istream &operator>>(istream &in, vector<T> &arr) {
  for (T &cnt : arr) {
    in >> cnt;
  }
  return in;
};
int depth[MAXN], used[MAXN];
vector<long long> graph[MAXN];
vector<long long> ans[318];
int down = 0, up = 0;
vector<long long> cycle = {};
bool go(int v, int u) {
  if (v == u) {
    cycle.push_back(u);
    return true;
  }
  for (int w : graph[v]) {
    if (depth[w] == depth[v] + 1) {
      if (!go(w, u))
        cycle.clear();
      else {
        cycle.push_back(v);
        return true;
      }
    }
  }
  return false;
}
void dfs(int v, int p = -1) {
  if (p != -1) depth[v] = depth[p] + 1;
  ans[depth[v] % down].push_back(v);
  used[v] = 1;
  for (int u : graph[v]) {
    if (p == u) continue;
    if (used[u] && depth[v] - depth[u] >= down) {
      go(u, v);
      cout << 2 << "\n" << cycle.size() << "\n";
      for (auto i : cycle) {
        cout << i + 1 << " ";
      }
      exit(0);
    }
    if (!used[u]) dfs(u, v);
  }
}
void solve() {
  int n, m;
  cin >> n >> m;
  down = sqrt(n) + eps;
  up = abs(sqrt(n) - down) < eps ? sqrt(n) + eps : sqrt(n) + 1 + eps;
  for (int i = 0; i < m; ++i) {
    int v, u;
    cin >> v >> u;
    v--, u--;
    graph[v].push_back(u);
    graph[u].push_back(v);
  }
  dfs(0);
  int i_best = 0;
  for (int i = 0; i < down; ++i) {
    if (ans[i].size() > ans[i_best].size()) i_best = i;
  }
  cout << 1 << "\n";
  for (int j = 0; j < up; ++j) {
    cout << ans[i_best][j] + 1 << " ";
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout.precision(30);
  solve();
  return 0;
}
