#include <bits/stdc++.h>
using namespace std;
vector<int> adj1[100005], adj2[100005];
vector<int> grp[2];
int color[100005], par[100005];
bool vis[100005], good[100005];
bool has_cycle = false;
vector<int> cycle;
int n, m, k, cnt = 0;
void dfs(int x) {
  cnt++;
  if (cnt <= k) good[x] = true;
  vis[x] = true;
  for (int y : adj1[x]) {
    if (!vis[y]) dfs(y);
  }
}
void dfs2(int x, int p) {
  if (has_cycle) return;
  par[x] = p;
  grp[color[x]].push_back(x);
  vis[x] = true;
  for (int y : adj2[x]) {
    if (has_cycle) return;
    if (y == par[x])
      continue;
    else if (vis[y]) {
      has_cycle = true;
      cycle.push_back(y);
      int cur = x;
      while (cur != y) {
        cycle.push_back(cur);
        cur = par[cur];
      }
      return;
    } else {
      color[y] = 1 - color[x];
      dfs2(y, x);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m >> k;
  vector<pair<int, int>> edges;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    edges.push_back({x, y});
    adj1[x].push_back(y);
    adj1[y].push_back(x);
  }
  memset(vis, 0, sizeof vis);
  dfs(1);
  for (auto p : edges) {
    int x = p.first, y = p.second;
    if (good[x] && good[y]) {
      adj2[x].push_back(y);
      adj2[y].push_back(x);
    }
  }
  color[1] = 0;
  memset(vis, false, sizeof vis);
  dfs2(1, 0);
  if (has_cycle) {
    cout << 2 << "\n";
    cout << cycle.size() << "\n";
    for (int i : cycle) cout << i << " ";
  } else {
    cout << 1 << "\n";
    if (grp[1].size() > grp[0].size()) {
      for (int i = 0; i < (k + 1) / 2; i++) cout << grp[1][i] << " ";
    } else {
      for (int i = 0; i < (k + 1) / 2; i++) cout << grp[0][i] << " ";
    }
  }
}
