#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using pii = pair<int, int>;
using vchar = vector<char>;
using vvchar = vector<vchar>;
using vint = vector<int>;
using vint64 = vector<int64>;
using vvint = vector<vint>;
using vbool = vector<bool>;
using vpii = vector<pii>;
template <typename T>
T sqr(T x) {
  return x * x;
}
template <typename T>
T gcd(T a, T b) {
  return b == 0 ? a : gcd(b, a % b);
}
pair<int, vint> solveD(vvint g, int k) {
  enum { NOT_VISITED, STARTED, FINISHED };
  const int n = g.size();
  vint depth(n, -1);
  depth[0] = 0;
  vint parent(n, -1);
  vint loopState(n, NOT_VISITED);
  pair<int, vint> result;
  result.first = 0;
  std::function<void(int)> DFS = [&](int v) {
    loopState[v] = STARTED;
    const int previous = parent[v];
    if (result.first != 0) return;
    int backVertex = -1;
    int backDepth = -1;
    for (auto to : g[v]) {
      if (to == previous) continue;
      if (loopState[to] == STARTED && depth[to] > backDepth) {
        backVertex = to;
        backDepth = depth[to];
      }
    }
    if (backVertex != -1) {
      vint loop;
      for (int u = v; u != backVertex; u = parent[u]) {
        loop.push_back(u);
      }
      loop.push_back(backVertex);
      reverse(std::begin(loop), std::end(loop));
      assert(depth[v] - depth[backVertex] + 1 == loop.size());
      const int loopLength = loop.size();
      if (loopLength > k) {
        result.first = 1;
        for (int i = 0; i < loop.size(); i += 2) {
          result.second.push_back(loop[i]);
        }
        result.second.resize((k + 1) / 2);
      } else {
        result.first = 2;
        result.second = loop;
      }
      return;
    }
    for (auto to : g[v]) {
      if (loopState[to] == NOT_VISITED) {
        parent[to] = v;
        depth[to] = depth[v] + 1;
        DFS(to);
        if (result.first != 0) return;
      }
    }
    loopState[v] = FINISHED;
  };
  DFS(0);
  if (result.first != 0) {
    return result;
  }
  vint colors(n, -1);
  std::function<void(int, int)> biColor = [&](int v, int color) {
    colors[v] = color;
    for (auto to : g[v]) {
      if (colors[to] == -1) {
        biColor(to, 1 - color);
      }
    }
  };
  biColor(0, 0);
  int colorCount[2] = {0};
  for (int i = 0; i < n; ++i) {
    colorCount[colors[i]]++;
  }
  const int bestColor = colorCount[0] > colorCount[1] ? 0 : 1;
  result.first = 1;
  for (int i = 0; i < n; ++i) {
    if (colors[i] == bestColor) {
      result.second.push_back(i);
    }
  }
  result.second.resize((k + 1) / 2);
  return result;
}
int main() {
  int T = 1;
  std::ios::sync_with_stdio(false);
  while (T--) {
    int n;
    cin >> n;
    ;
    int m;
    cin >> m;
    ;
    int k;
    cin >> k;
    ;
    vvint g(n);
    while (m--) {
      int u;
      cin >> u;
      ;
      int v;
      cin >> v;
      ;
      u--, v--;
      g[u].push_back(v);
      g[v].push_back(u);
    }
    auto result = solveD(g, k);
    assert(result.first == 1 || result.first == 2);
    cout << result.first << endl;
    for (int& v : result.second) {
      v++;
    }
    if (result.first == 2) {
      cout << result.second.size() << endl;
    }
    std::copy(std::begin(result.second), std::end(result.second),
              ostream_iterator<int>(cout, " "));
    cout << endl;
  }
  return 0;
}
