#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const long long INF = 1e18;
const long double PI = acos((long double)-1);
const int xd[4] = {1, 0, -1, 0}, yd[4] = {0, 1, 0, -1};
const int MN = 1e5 + 5;
int N, M, dis[MN], par[MN], sq;
bool vis[MN], added[MN];
vector<int> adj[MN], res, ind;
void dfs(int u, int p) {
  vis[u] = true;
  bool bad = false;
  for (int check : adj[u]) {
    if (check == p) continue;
    if (vis[check] && dis[check] < dis[u] && dis[u] - dis[check] + 1 >= sq) {
      int curr = u;
      while (curr != check) {
        res.push_back(curr);
        curr = par[curr];
      }
      res.push_back(check);
      return;
    }
    if (vis[check]) {
      if (added[check]) bad = true;
      continue;
    }
    dis[check] = dis[u] + 1;
    par[check] = u;
    dfs(check, u);
    if (res.size()) return;
    if (added[check]) bad = true;
  }
  if (!bad) added[u] = true, ind.push_back(u);
}
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> M;
  sq = (int)ceil(sqrt(N));
  for (int i = 1; i <= M; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  dfs(1, -1);
  if (res.size()) {
    cout << 2 << "\n" << res.size() << "\n";
    for (auto u : res) cout << u << " ";
    return 0;
  }
  cout << 1 << "\n";
  for (int i = 0; i < sq; i++) cout << ind[i] << " ";
}
