#include <bits/stdc++.h>
const int N = 4e5 + 5;
using namespace std;
int n, m, k;
int d[N], mi = 1e9, st[N], top;
int cl[N], dem[3];
vector<int> a[N], s;
void dfs(int p, int u) {
  if (u == 1)
    cl[u] = 0;
  else
    cl[u] = 1 - cl[p];
  dem[cl[u]]++;
  s.push_back(u);
  d[u] = s.size();
  for (int v : a[u])
    if (v != p) {
      if (!d[v])
        dfs(u, v);
      else if (d[u] >= d[v]) {
        if (mi > d[u] - d[v] + 1) {
          mi = d[u] - d[v] + 1;
          top = 0;
          for (int i = d[v] - 1; i < d[u]; i++) st[++top] = s[i];
        }
        if (d[u] - d[v] + 1 <= k) {
          cout << "2\n" << d[u] - d[v] + 1 << '\n';
          for (int i = d[v] - 1; i < d[u]; i++) cout << s[i] << ' ';
          exit(0);
        }
      }
    }
  s.pop_back();
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    a[u].push_back(v);
    a[v].push_back(u);
  }
  dfs(1, 1);
  cout << "1\n";
  int cnt;
  if (k & 1)
    cnt = k / 2 + 1;
  else
    cnt = k / 2;
  if (mi != 1e9) {
    for (int i = 1; i <= top; i += 2) {
      if (!cnt) break;
      cout << st[i] << ' ';
      cnt--;
    }
  } else {
    int cd;
    if (dem[0] > dem[1])
      cd = 0;
    else
      cd = 1;
    for (int i = 1; i <= n; i++) {
      if (cnt == 0) break;
      if (cl[i] == cd) {
        cout << i << ' ';
        cnt--;
      }
    }
  }
}
