#include <bits/stdc++.h>
using namespace std;
int cyc = 1e9;
int f = 0;
int k;
vector<vector<int>> v;
int a[2];
vector<int> vis, depth, par;
int dfs(int x) {
  for (int i = 0; i < v[x].size(); i++) {
    if (v[x][i] == par[x])
      continue;
    else if (vis[v[x][i]] == 1) {
      if (k > abs(depth[x] - depth[v[x][i]])) {
        f = 1;
        cout << 2 << "\n";
        cout << abs(depth[x] - depth[v[x][i]]) + 1 << "\n";
        int j = v[x][i];
        cout << v[x][i] << " ";
        while (x != j) {
          cout << x << " ";
          x = par[x];
        }
        exit(0);
      } else {
        cyc = min(cyc, abs(depth[x] - depth[v[x][i]] + 1));
        if (cyc == abs(depth[x] - depth[v[x][i]] + 1)) {
          a[0] = x;
          a[1] = v[x][i];
        }
      }
    } else {
      depth[v[x][i]] = depth[x] + 1;
      vis[v[x][i]] = 1;
      par[v[x][i]] = x;
      dfs(v[x][i]);
    }
  }
  return 0;
}
int dfs1(int x) {
  for (int i = 0; i < v[x].size(); i++) {
    if (vis[v[x][i]] == 1)
      continue;
    else {
      depth[v[x][i]] = depth[x] + 1;
      vis[v[x][i]] = 1;
      dfs1(v[x][i]);
    }
  }
  return 0;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m >> k;
  int u, uu;
  v.resize(n + 1);
  vis.resize(n + 1, 0);
  par.resize(n + 1, 0);
  depth.resize(n + 1, -1);
  for (int i = 0; i < m; i++) {
    cin >> u >> uu;
    v[u].push_back(uu);
    v[uu].push_back(u);
  }
  vis[1] = 1;
  depth[1] = 0;
  dfs(1);
  if (f == 0) {
    cout << 1 << "\n";
    if (cyc == 1e9) {
      for (int i = 1; i <= n; i++) {
        depth[i] = 0;
        vis[i] = 0;
      }
      vis[1] = 1;
      dfs(1);
      a[0] = 0;
      a[1] = 0;
      for (int i = 1; i <= n; i++) {
        if (depth[i] % 2 == 0)
          a[0]++;
        else
          a[1]++;
      }
      if (a[0] > a[1]) {
        int cnt = 0;
        int h = k + 1;
        h /= 2;
        for (int i = 1; i <= n; i++) {
          if (depth[i] % 2 == 0) {
            cnt++;
            cout << i << " ";
          }
          if (cnt == h) return 0;
        }
      } else {
        int cnt = 0;
        int h = k + 1;
        h /= 2;
        for (int i = 1; i <= n; i++) {
          if (depth[i] % 2 == 1) {
            cnt++;
            cout << i << " ";
          }
          if (cnt == h) return 0;
        }
      }
    }
    vector<int> ans;
    int j = 0;
    if (depth[a[0]] < depth[a[1]]) swap(a[0], a[1]);
    while (a[0] != a[1]) {
      if (j % 2 == 0) ans.push_back(a[0]);
      j++;
      a[0] = par[a[0]];
      int h = k + 1;
      h /= 2;
      if (ans.size() == h) break;
    }
    for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
  }
  return 0;
}
