#include <bits/stdc++.h>
using namespace std;
template <typename T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(long long &x) { cin >> x; }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <typename T, typename... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <typename T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
template <typename T>
void _W(const vector<T> &x) {
  for (auto i = x.cbegin(); i != x.cend(); i++) {
    if (i != x.cbegin()) putchar(' ');
    _W(*i);
  }
}
void W() {}
template <typename T, typename... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
template <class T>
inline void maz(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void miz(T &a, T b) {
  if (a > b) a = b;
}
template <class T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
const int N = 1e5 + 10;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
int n, m;
int sqn;
vector<int> G[N];
bool mis() {
  static int deg[N];
  static int sta[N];
  int cnt = 0;
  for (int i = 0; i < n; i++) deg[i] = G[i].size();
  priority_queue<std::pair<int, int> > Q;
  for (int i = 0; i < n; i++) Q.push(std::make_pair(-deg[i], i));
  while (!Q.empty()) {
    const auto t = Q.top();
    Q.pop();
    const int x = t.second, d = -t.first;
    if (deg[x] != d) continue;
    if (sta[x] != 0) continue;
    sta[x] = 1;
    cnt++;
    if (cnt == sqn) break;
    for (auto y : G[x]) {
      if (sta[y] != -1) {
        assert(sta[y] == 0);
        sta[y] = -1;
        for (auto z : G[y])
          if (sta[z] == 0) {
            --deg[z];
            Q.push(std::make_pair(-deg[z], z));
          }
      }
    }
  }
  if (cnt != sqn) return false;
  puts("1");
  for (int i = 0; i < n; i++)
    if (sta[i] == 1) printf("%d ", i + 1);
  puts("");
  return true;
}
int vis[N], vtop;
int par[N], dep[N];
void print(int x, int y) {
  puts("2");
  printf("%d\n", dep[x] - dep[y] + 1);
  while (x != y) {
    printf("%d ", x + 1);
    x = par[x];
  }
  printf("%d\n", y + 1);
}
void dfs(int x, int d) {
  dep[x] = d;
  vis[x] = vtop;
  for (auto y : G[x])
    if (vis[y] == vtop) {
      if (dep[x] - dep[y] + 1 >= sqn) {
        print(x, y);
        exit(0);
      }
    } else {
      par[y] = x;
      dfs(y, d + 1);
    }
}
bool find_cycle(int rt) {
  vtop++;
  dfs(rt, 0);
  return false;
}
int main() {
  R(n, m);
  for (int i = 0; i < m; i++) {
    int x, y;
    R(x, y);
    x--;
    y--;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  sqn = sqrt(n);
  while (sqn * sqn < n) sqn++;
  if (mis()) return 0;
  int T = 1;
  vector<int> V;
  for (int i = 0; i < n; i++) V.push_back(i);
  srand(time(NULL));
  std::random_device rd;
  std::mt19937 g(rd());
  shuffle((V).begin(), (V).end(), g);
  while (T--)
    if (find_cycle(V[T])) break;
  return 0;
}
