#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
int gcd(int A, int B) {
  if (!B) return A;
  return gcd(B, A % B);
}
const int MAXN = 2 * 1e5 + 5;
int n, m, k;
vector<int> dfs(MAXN, -1), cyc, s;
vector<vector<int>> col(2);
vector<vector<int>> adj(MAXN);
bool visit(int v, int u) {
  dfs[v] = s.size();
  col[dfs[v] % 2].push_back(v);
  s.push_back(v);
  int low = -1;
  for (int x : adj[v]) {
    if (x == u) continue;
    if (dfs[x] != -1 && dfs[v] - dfs[x] > 1) low = max(low, dfs[x]);
  }
  if (low != -1) {
    for (int i = low; i <= dfs[v]; i++) cyc.push_back(s[i]);
    return 1;
  }
  for (int x : adj[v]) {
    if (x == u) continue;
    if (dfs[x] == -1) {
      if (visit(x, v)) return 1;
    }
  }
  s.pop_back();
  return 0;
}
int main() {
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int v, u;
    cin >> v >> u;
    adj[v].push_back(u);
    adj[u].push_back(v);
  }
  visit(1, 0);
  if (cyc.empty()) {
    if (col[1].size() > col[0].size()) swap(col[1], col[0]);
    cout << 1 << '\n';
    for (int i = 0; i < (k + 1) / 2; i++) cout << col[0][i] << " ";
  } else {
    if ((int)(cyc.size()) > k) {
      cout << 1 << '\n';
      for (int i = 0; i < (k + 1) / 2; i++) {
        cout << cyc[2 * i] << " ";
      }
    } else {
      cout << 2 << '\n';
      cout << cyc.size() << '\n';
      for (int x : cyc) cout << x << " ";
    }
  }
}
