#include <bits/stdc++.h>
using namespace std;
template <class T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
struct Edge {
  int from, to;
  Edge(){};
  Edge(int from, int to) : from(from), to(to) {}
  void scanFrom(std::istream& strm, int base = 1) {
    strm >> from >> to;
    if (base == 1) --from, --to;
  }
  Edge reverse() const { return Edge(to, from); }
};
inline std::istream& operator>>(std::istream& strm, Edge& t) {
  t.scanFrom(strm);
  return strm;
}
template <typename T>
struct WeightedEdge {
  int from, to;
  T _weight;
  WeightedEdge(){};
  WeightedEdge(int from, int to, T weight)
      : from(from), to(to), _weight(weight) {}
  void scanFrom(std::istream& strm, int base = 1) {
    strm >> from >> to >> _weight;
    if (base == 1) --from, --to;
  }
  T weight() const { return _weight; }
  WeightedEdge reverse() const { return WeightedEdge(to, from, _weight); }
};
template <typename T>
inline std::istream& operator>>(std::istream& strm, WeightedEdge<T>& t) {
  t.scanFrom(strm);
  return strm;
}
template <typename Edge>
class Digraph {
  int _E, _V;
  vector<vector<Edge>> _adjacencyList;

 public:
  int E() const { return _E; }
  int V() const { return _V; }
  int size() const { return _V; }
  Digraph() : _V(0), _E(0){};
  Digraph(int V, int E = 0) : _V(V), _E(E) { _adjacencyList.resize(V); }
  void addEdge(const Edge& e) {
    _adjacencyList[e.from].push_back(e);
    ++_E;
  }
  void addUndirectedEdge(const Edge& e) {
    _adjacencyList[e.from].push_back(e);
    _adjacencyList[e.to].push_back(e.reverse());
    ++_E;
  }
  void addNode() {
    ++_V;
    _adjacencyList.push_back(vector<Edge>());
  }
  void scanFrom(std::istream& strm, int base = 1) {
    if (_V == 0) strm >> _V;
    if (_E == 0) strm >> _E;
    _adjacencyList.resize(_V);
    for (int i = 0; i < _E; ++i) {
      Edge e;
      e.scanFrom(cin, base);
      assert(0 <= e.from < _V);
      assert(0 <= e.to < _V);
      addEdge(e);
    }
  }
  vector<Edge> operator[](int u) const { return _adjacencyList[u]; }
  vector<vector<Edge>>& adjacencyList() { return _adjacencyList; }
};
template <typename Edge>
inline std::istream& operator>>(std::istream& strm, Digraph<Edge>& t) {
  t.scanFrom(strm);
  return strm;
}
int main() {
  int V, E;
  cin >> V >> E;
  Digraph<Edge> G(V, E);
  for (int i = 0; i < (int)(E); ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    --u, --v;
    G.addUndirectedEdge(Edge(u, v));
  }
  int sq = ceil(sqrt(V));
  vector<int> depth(V, -1);
  vector<bool> independent(V, false);
  function<void(int, int)> printCycle = [&](int s, int u) {
    printf("%d ", u + 1);
    if (u == s) return;
    for (Edge& e : G[u]) {
      if (depth[e.to] == depth[u] - 1) printCycle(s, e.to);
    }
  };
  function<void(int, int)> dfs = [&](int u, int d) {
    depth[u] = d;
    bool ind = true;
    int mind = d, anc = u;
    for (Edge& e : G[u]) {
      if (depth[e.to] == -1) dfs(e.to, d + 1);
      if (depth[e.to] < depth[u]) {
        if (chmin(mind, depth[e.to])) anc = e.to;
        continue;
      }
      ind &= !independent[e.to];
    }
    if (d - mind >= sq - 1) {
      cout << 2 << endl;
      cout << d - mind + 1 << endl;
      printCycle(anc, u);
      exit(0);
    }
    independent[u] = ind;
  };
  dfs(0, 0);
  cout << 1 << endl;
  int c = 0;
  for (int u = 0; u < (int)(V); ++u) {
    if (c < sq && independent[u]) {
      printf("%d ", u + 1);
      ++c;
    }
  }
  cout << endl;
  return 0;
}
