#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int maxn = 1e5 + 3;
int n, m, k;
vector<int> adj[maxn];
void read() {
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
}
int depth[maxn], par[maxn];
int a = -1, b = -1;
void dfs(int ver) {
  for (auto i : adj[ver]) {
    if (!depth[i]) {
      depth[i] = depth[ver] + 1;
      par[i] = ver;
      dfs(i);
    } else if (depth[i] < depth[ver] - 1) {
      if (a == -1 || (depth[ver] - depth[i] + 1 < depth[a] - depth[b] + 1))
        a = ver, b = i;
    }
  }
}
vector<int> v1, v2;
void dfs1(int ver, int par, int d) {
  if (d % 2 == 0)
    v1.push_back(ver);
  else
    v2.push_back(ver);
  for (auto i : adj[ver])
    if (i != par) dfs1(i, ver, d + 1);
}
void solve() {
  par[1] = -1;
  depth[1] = 1;
  dfs(1);
  if (a == -1) {
    dfs1(1, -1, 1);
    if ((int)v1.size() < (int)v2.size()) swap(v1, v2);
    cout << 1 << '\n';
    for (int i = 0; i < k / 2 + k % 2; i++) cout << v1[i] << " ";
    cout << '\n';
    return;
  }
  vector<int> cycle;
  while (a != b) {
    cycle.push_back(a);
    a = par[a];
  }
  cycle.push_back(b);
  if ((int)cycle.size() <= k) {
    cout << 2 << '\n';
    cout << (int)cycle.size() << '\n';
    for (auto i : cycle) cout << i << " ";
    cout << '\n';
    return;
  }
  int p = k / 2 + k % 2;
  cout << 1 << '\n';
  for (int i = 0; p > 0; i += 2) {
    cout << cycle[i] << " ";
    p--;
  }
  cout << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  read();
  solve();
}
