#include <bits/stdc++.h>
using namespace std;
bool istrue[100005];
vector<int> a[100005];
int par[100005];
vector<long long int> v, vv;
int n, m, k;
vector<long long int> ds[2];
bool cc = false, cb = false;
int siz = 1000000001;
int ti[100005];
long long int dd[100005];
int tm1 = 0;
void dfs(int s, int dis) {
  istrue[s] = true;
  ds[dis % 2].push_back(s);
  ti[s] = ++tm1;
  for (auto u : a[s]) {
    if (!istrue[u]) {
      istrue[u] = true;
      par[u] = s;
      dd[u] = dd[s] + 1;
      dfs(u, dis + 1);
    } else if (ti[u] < ti[s] && !cb) {
      if (u != par[s]) {
        if (dd[s] - dd[u] + 1 < siz || siz == 1000000001) {
          long long int x = s;
          vv.push_back(x);
          while (x != u) {
            x = par[x];
            vv.push_back(x);
          }
          siz = (long long int)vv.size();
          v.clear();
          for (auto u : vv) v.push_back(u);
          if (siz <= k) cb = true;
          vv.clear();
        }
        cc = true;
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  while (t--) {
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
      int x, y;
      cin >> x >> y;
      a[x].push_back(y);
      a[y].push_back(x);
    }
    dd[0] = 0;
    dfs(1, 0);
    if (cc) {
      if ((long long int)v.size() <= k) {
        cout << "2"
             << "\n"
             << (long long int)v.size() << "\n";
        for (auto u : v) cout << u << " ";
        cout << "\n";
      } else {
        cout << "1"
             << "\n";
        for (long long int i = 0; i < (k + 1) / 2; i++) cout << v[2 * i] << " ";
        cout << "\n";
      }
    } else {
      cout << "1"
           << "\n";
      if ((long long int)ds[0].size() >= (k + 1) / 2) {
        for (int i = 0; i < (k + 1) / 2; i++) cout << ds[0][i] << " ";
      } else {
        for (int i = 0; i < (k + 1) / 2; i++) cout << ds[1][i] << " ";
      }
      cout << "\n";
    }
  }
  return 0;
}
