#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 1;
int n, m, k, col[maxn], dist[maxn];
vector<int> adj[maxn], path;
void dfs(int cur = 1, int d = 1, int c = 0) {
  if (dist[cur]) return;
  dist[cur] = d;
  col[cur] = c;
  path.push_back(cur);
  int back = -1;
  for (int nbr : adj[cur]) {
    if (dist[nbr] && dist[cur] - dist[nbr] > 1) {
      back = max(back, dist[nbr]);
    }
  }
  if (back != -1) {
    if (dist[cur] - back + 1 <= k) {
      cout << "2\n" << dist[cur] - back + 1 << '\n';
      for (int i = (back - 1);
           (((back - 1) < (dist[cur]) ? 1 : -1) > 0 ? i < (dist[cur])
                                                    : i > (dist[cur]));
           i += ((back - 1) < (dist[cur]) ? 1 : -1)) {
        cout << path[i] << ' ';
      }
    } else {
      cout << "1\n";
      for (int i = (0); ((1) > 0 ? i < ((k + 1) / 2) : i > ((k + 1) / 2));
           i += (1)) {
        cout << path[back - 1 + 2 * i] << ' ';
      }
    }
    exit(0);
  }
  for (int nbr : adj[cur]) dfs(nbr, d + 1, !c);
  path.pop_back();
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m >> k;
  for (int i = (0); ((1) > 0 ? i < (m) : i > (m)); i += (1)) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  dfs();
  vector<int> ans[2];
  for (int i = (1); (((1) < (n + 1) ? 1 : -1) > 0 ? i < (n + 1) : i > (n + 1));
       i += ((1) < (n + 1) ? 1 : -1)) {
    ans[col[i]].push_back(i);
  }
  cout << "1\n";
  if (ans[0].size() > ans[1].size()) {
    int j = 0;
    for (int i : ans[0]) {
      cout << i << ' ';
      j++;
      if (j == (k + 1) / 2) break;
    }
  } else {
    int j = 0;
    for (int i : ans[1]) {
      cout << i << ' ';
      j++;
      if (j == (k + 1) / 2) break;
    }
  }
}
