#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
constexpr int MOD = 1000000007;
constexpr ll INF = (1LL << 61) - 1;
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
void fail(T v) {
  cout << v << endl;
  exit(0);
}
int N, M, K, ct = 0, from, to, mn = MOD;
bool b = 1;
vector<int> G[101010], par, dep, col;
void dfs(int i) {
  for (int& e : G[i]) {
    if (e == par[i]) continue;
    if (~par[e]) {
      if (dep[i] > dep[e] && chmin(mn, dep[i] - dep[e] + 1)) {
        from = i;
        to = e;
      }
      continue;
    }
    par[e] = i;
    dep[e] = dep[i] + 1;
    dfs(e);
  }
}
void bip(int i, int c) {
  col[i] = c;
  if (c == 1) ct++;
  for (int& e : G[i]) {
    if (~col[e]) {
      b &= col[e] == 1 ^ c;
      continue;
    }
    bip(e, 1 ^ c);
  }
}
void solve() {
  cin >> N >> M >> K;
  par.assign(N, -1);
  dep.resize(N);
  for (int i = 0; i < (int)(M); ++i) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  col.assign(N, -1);
  bip(0, 0);
  if (b) {
    ct = ct >= (K + 1) / 2;
    cout << 1 << endl;
    int r = 0;
    for (int i = 0; i < (int)(N); ++i) {
      if (col[i] != ct) continue;
      r++;
      cout << i + 1 << " ";
      if (r == (K + 1) / 2) break;
    }
    cout << endl;
    return;
  }
  par[0] = -2;
  dfs(0);
  vector<int> res;
  res.push_back(from);
  while (from != to) {
    from = par[from];
    res.push_back(from);
  }
  if (res.size() <= K) {
    cout << 2 << endl;
    cout << res.size() << endl;
    for (int i = 0; i < (int)(res.size()); ++i) cout << res[i] + 1 << " ";
    cout << endl;
  } else {
    cout << 1 << endl;
    for (int i = 0; i < (int)((K + 1) / 2); ++i) cout << res[2 * i] + 1 << " ";
    cout << endl;
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  solve();
  return 0;
}
