#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
template <typename T, typename second>
ostream& operator<<(ostream& s, pair<T, second>& p) {
  s << '{' << p.first << ", " << p.second << '}';
  return s;
}
template <typename T>
ostream& operator<<(ostream& s, vector<T>& v) {
  if (v.empty()) {
    s << "[]";
    return s;
  }
  s << '[';
  for (int i = 0; i < v.size() - 1; i++) s << v[i] << ", ";
  s << v.back() << ']';
  return s;
}
vector<int> adj[100001];
unordered_set<int> indep;
int depth[100001], par[100001];
int n, a, b, m, sq;
bool vis[100001];
void dfs(int st, int dep, int pr) {
  vis[st] = true;
  depth[st] = dep;
  par[st] = pr;
  int cnt = 0;
  int top = 0;
  bool ok = true;
  for (auto x : adj[st]) {
    if (!vis[x]) {
      dfs(x, dep + 1, st);
    } else {
      if (depth[x] < depth[top]) top = x;
      cnt++;
    }
  }
  if (depth[st] - depth[top] >= sq - 1) {
    puts("2");
    int nxt = st;
    vector<int> ans;
    while (nxt != par[top]) {
      ans.push_back(nxt);
      nxt = par[nxt];
    }
    printf("%d\n", (int)ans.size());
    for (auto x : ans) printf("%d ", x);
    printf("\n");
    exit(0);
  }
  for (auto x : adj[st]) {
    if (depth[x] < dep) continue;
    if (indep.find(x) != indep.end()) {
      ok = false;
      break;
    }
  }
  if (ok) indep.insert(st);
}
int main() {
  scanf("%d%d", &n, &m);
  depth[0] = INT32_MAX;
  sq = ceil(sqrt(n));
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &a, &b);
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  dfs(1, 0, 0);
  puts("1");
  int cnt = 0;
  for (auto x : indep) {
    printf("%d ", x);
    cnt++;
    if (cnt == sq) break;
  }
  printf("\n");
  return 0;
}
