#include <bits/stdc++.h>
using namespace std;
bool prime[2000005];
vector<long long> primes;
void seive() {
  long long sq = sqrt(2000005);
  for (int i = 4; i < 2000005; i += 2) prime[i] = true;
  for (int i = 3; i <= sq; i += 2) {
    if (prime[i] == false) {
      for (int j = i * i; j < 2000005; j += i) {
        prime[j] = true;
      }
    }
  }
  for (int i = 2; i < 2000005; i++) {
    if (prime[i] == false) primes.push_back(i);
  }
}
bool vis[2000005];
set<long long> s;
long long ans[2000005], a[2000005];
vector<long long> v[2000005];
long long dep[2000005];
vector<long long> cycle;
long long n, m, k, sq;
long long ok = 1;
long long st = -1;
long long en = -1;
long long par[2000005];
void dfs(long long sn) {
  vis[sn] = 1;
  for (auto i : v[sn]) {
    if (vis[i] && i != par[sn]) {
      long long x = abs(dep[sn] - dep[i]) + 1;
      if (x >= sq) {
        st = i;
        en = sn;
      }
    }
    if (!vis[i]) {
      par[i] = sn;
      dep[i] = dep[sn] + 1;
      dfs(i);
    }
  }
}
long long color[2000005];
long long lev[2000005];
void bicolor(long long sn, long long c) {
  vis[sn] = 1;
  color[sn] = c;
  for (auto i : v[sn]) {
    if (!vis[i]) {
      bicolor(i, !c);
    }
  }
}
bool cmp(int a, int b) { return dep[a] > dep[b]; }
int main() {
  int t = 1;
  while (t--) {
    cin >> n;
    cin >> m;
    for (int i = 1; i <= m; i++) {
      long long x, y;
      cin >> x >> y;
      v[x].push_back(y);
      v[y].push_back(x);
    }
    sq = sqrt(n);
    if (sq * sq != n) sq++;
    for (int i = 1; i <= n; i++) {
      sort(v[i].begin(), v[i].end());
      dep[i] = 1234567789;
      lev[i] = 0;
    }
    dep[1] = 1;
    dfs(1);
    if (st != -1) {
      while (st != en) {
        cycle.push_back(st);
        st = par[st];
      }
      cycle.push_back(en);
      cout << 2 << endl;
      cout << cycle.size() << endl;
      for (auto i : cycle) cout << i << " ";
      cout << endl;
    } else {
      cout << 1 << endl;
      memset(vis, false, sizeof(vis));
      vector<long long> inone, inzero;
      for (int i = 1; i <= n; i++) inone.push_back(i);
      sort(inone.begin(), inone.end(), cmp);
      for (int i = 0; i < inone.size(); i++) {
        if (vis[inone[i]] == true) continue;
        inzero.push_back(inone[i]);
        for (auto j : v[inone[i]]) vis[j] = 1;
        if (inzero.size() == sq) break;
      }
      for (auto i : inzero) cout << i << " ";
      cout << endl;
    }
  }
}
