#include <bits/stdc++.h>
using namespace std;
vector<int> V[500001], V1[500001], V2[500001];
int G[500001], De[500001], P[20][500001], Deg[500001], r;
void dfs(int d, int p) {
  for (int i = 0; i < V[d].size(); i++) {
    int a = V[d][i];
    if (a != p && G[a] == 1) {
      G[a] = 0;
      De[a] = De[d] + 1;
      P[0][a] = d;
      V1[a].push_back(d);
      V1[d].push_back(a);
      dfs(a, d);
    }
  }
}
void Sol1(int n) {
  cout << 1 << "\n";
  priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>,
                 greater<pair<int, pair<int, int>>>>
      Ve;
  for (int i = 1; i <= n; i++) {
    G[i] = 1;
    Ve.push({Deg[i], {rand(), i}});
  }
  int k = 0;
  while (k < r && Ve.size() > 0) {
    int a = Ve.top().second.second;
    Ve.pop();
    if (G[a] == 1) {
      G[a] = 0;
      k++;
      cout << a << " ";
      for (int y = 0; y < V[a].size(); y++) {
        int b = V[a][y];
        if (G[b] == 1) {
          G[b] = 0;
          for (int u = 0; u < V[b].size(); u++) {
            int c = V[b][u];
            if (G[c] == 1) {
              Deg[c]--;
              Ve.push({Deg[c], {rand(), c}});
            }
          }
        }
      }
    }
  }
}
void Sol2(int a, int b, int l) {
  vector<int> R, R1;
  while (a != l) {
    R.push_back(a);
    a = P[0][a];
  }
  R.push_back(l);
  while (b != l) {
    R1.push_back(b);
    b = P[0][b];
  }
  for (int i = R1.size() - 1; i >= 0; i--) {
    R.push_back(R1[i]);
  }
  cout << 2 << "\n";
  cout << R.size() << "\n";
  for (int i = 0; i < R.size(); i++) {
    cout << R[i] << " ";
  }
}
int LCA(int a, int b) {
  if (De[b] > De[a]) {
    swap(a, b);
  }
  for (int i = 19; i >= 0; i--) {
    if (P[i][a] != -1 && De[P[i][a]] >= De[b]) {
      a = P[i][a];
    }
  }
  for (int i = 19; i >= 0; i--) {
    if (P[i][a] != -1 && P[i][b] != -1 && P[i][a] != P[i][b]) {
      a = P[i][b];
      b = P[i][b];
    }
  }
  if (a != b) {
    a = P[0][a];
  }
  return a;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m, a, b, l;
  long double nn;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    P[0][i] = -1;
    Deg[i] = 0;
    G[i] = 1;
  }
  for (int i = 0; i < m; i++) {
    cin >> a >> b;
    V[a].push_back(b);
    V[b].push_back(a);
    Deg[a]++;
    Deg[b]++;
  }
  De[1] = 0;
  G[1] = 0;
  dfs(1, -1);
  for (int i = 1; i < 20; i++) {
    for (int y = 1; y <= n; y++) {
      if (P[i - 1][y] == -1 || P[i - 1][P[i - 1][y]] == -1) {
        P[i][y] = -1;
      } else {
        P[i][y] = P[i - 1][P[i - 1][y]];
      }
    }
  }
  nn = n;
  r = ceil(sqrt(nn));
  for (int i = 1; i <= n; i++) {
    for (int y = 0; y < V[i].size(); y++) {
      a = V[i][y];
      l = LCA(i, a);
      int d = 1 + (De[a] - De[l]) + (De[i] - De[l]);
      if (d >= r) {
        Sol2(i, a, l);
        return 0;
      }
    }
  }
  Sol1(n);
}
