#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e5 + 3;
const long long INFF = (long long)5e18 + 7;
vector<int> edge[N];
int nd;
int id[N], used[N], siz[N];
void sol(int n) {
  set<pair<int, int>> st;
  for (int i = 1; i <= n; i++) {
    siz[i] = (int)edge[i].size();
    st.insert({siz[i], i});
  }
  vector<int> ans;
  while (!st.empty()) {
    int x = st.begin()->second;
    st.erase(st.begin());
    used[x] = 1;
    ans.push_back(x);
    for (int v : edge[x]) {
      if (used[v]) continue;
      used[v] = 1;
      st.erase({siz[v], v});
      for (int u : edge[v]) {
        if (used[u]) continue;
        st.erase({siz[u], u});
        siz[u]--;
        st.insert({siz[u], u});
      }
    }
  }
  nd = sqrt(n);
  if (nd * nd < n) nd++;
  if ((int)ans.size() < nd) return;
  printf("1\n");
  for (int i = 0; i < nd; i++) printf("%d%c", ans[i], " \n"[i == nd - 1]);
  exit(0);
}
int dep[N], prt[N];
map<int, pair<int, int>> mp[N];
void ot(int x, int y) {
  printf("2\n%d\n", dep[x] - dep[y] + 1);
  int cur = x;
  vector<int> ans;
  while (cur != y) {
    ans.push_back(cur);
    cur = prt[cur];
  }
  ans.push_back(y);
  for (int i = 0; i < (int)ans.size(); i++)
    printf("%d%c", ans[i], " \n"[i == (int)ans.size() - 1]);
  exit(0);
}
void ot2(int x, int y, int p1, int p2) {
  printf("2\n%d\n", dep[x] + dep[y] - 2 * dep[p1] + 2);
  vector<int> ans, ans2;
  ans.push_back(p2);
  int cur = x;
  while (cur != p1) {
    ans.push_back(cur);
    cur = prt[cur];
  }
  ans.push_back(p1);
  cur = y;
  while (cur != p1) {
    ans2.push_back(cur);
    cur = prt[cur];
  }
  reverse(ans2.begin(), ans2.end());
  for (int x : ans2) ans.push_back(x);
  for (int i = 0; i < (int)ans.size(); i++)
    printf("%d%c", ans[i], " \n"[i == (int)ans.size() - 1]);
  exit(0);
}
void dfs(int u, int pa, int dpt) {
  dep[u] = dpt;
  prt[u] = pa;
  for (int v : edge[u]) {
    if (v == pa) continue;
    if (dep[v]) {
      continue;
    } else {
      dfs(v, u, dpt + 1);
      mp[id[v]].erase(u);
      if (mp[id[u]].size() < mp[id[v]].size()) swap(id[u], id[v]);
      for (auto x : mp[id[v]]) {
        if (mp[id[u]].find(x.first) != mp[id[u]].end()) {
          if (x.second.first + mp[id[u]][x.first].first -
                  2 * (dpt - dep[x.first]) >=
              nd) {
            ot2(x.second.second, mp[id[u]][x.first].second, u, x.first);
          }
          mp[id[u]][x.first] = max(mp[id[u]][x.first], x.second);
        } else {
          mp[id[u]][x.first] = x.second;
        }
      }
    }
  }
  for (int v : edge[u]) {
    if (dep[v] > dpt) continue;
    if (dpt - dep[v] + 1 >= nd) {
      ot(u, v);
    }
    mp[id[u]][v] = max(mp[id[u]][v], make_pair(dpt - dep[v] + 1, u));
  }
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    edge[u].push_back(v);
    edge[v].push_back(u);
  }
  sol(n);
  for (int i = 1; i <= n; i++) id[i] = i;
  dfs(1, 0, 1);
  assert(0);
  return 0;
}
