EBAAAN

#include<bits/stdc++.h>

#define endl "\n"
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

constexpr int N = 1e5 + 5;

int n, m, a, b, height[N], par[N], cur = 0;
set<int> gr[N];

vector<int> cyc;

void dfs(int v = 1, int p = -1) {
  par[v] = p;
  if (p == -1)
    height[v] = 1;
  else
    height[v] = height[p] + 1;
  for (int u: gr[v]) {
    if (u != p) {
      if (height[u] == 0)
        dfs(u, v);
      else if (cur < height[v] - height[u] + 1) {
        cur = height[v] - height[u] + 1;
        cyc.clear();
        cyc.push_back(u);
        cyc.push_back(v);
      }
    }
  }
}

void Solve() {
  //freopen("zhopa.txt", "r", stdin);
  unsigned seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  mt19937 Mrand(seed);
  cin >> n >> m;
  while(m--) {
    cin >> a >> b;
    gr[a].insert(b);
    gr[b].insert(a);
  }
  int num = ceil(sqrt(n));
  dfs();
  if (cyc.size())
    while(par[cyc.back()] != cyc.front())
      cyc.push_back(par[cyc.back()]);
  if (cyc.size() >= num) {
    cout << 2 << endl << cyc.size() << endl;
    for (int ver: cyc) {
      cout << ver << " ";
    }
    return;
  }
  while(true) {
    vector<int> vec;
    set<int> st;
    int iter = 0;
    while(iter < n && vec.size() < num) {
      int v = (Mrand() % n) + 1;
      if (st.count(v) == 0 && gr[v].size() < n / 2 + vec.size()) {
        bool good = 1;
        for (int val: vec) {
          if (gr[v].count(val)) {
            good = 0;
            break;
          }
        }
        if (good) {
          vec.push_back(v);
          st.insert(v);
        }
        iter++;
      }
    }
    if (vec.size() == num) {
      cout << 1 << endl;
      for (int val: vec) {
        cout << val << " ";
      }
      return;
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  //auto start = chrono::high_resolution_clock::now();
    Solve();
  //auto end = chrono::high_resolution_clock::now();
  //cout << endl << (chrono::duration_cast<chrono::duration<double>>(end - start)).count();
  return 0;
}