#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
const long long mod = 1e9 + 7;
long double PI = acosl(-1);
const long long infl = 1e15;
const int inf = 1e9;
const int nmax = 1e5 + 5;
const int MAXLG = log2(nmax) + 1;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int depth[nmax];
vector<int> g[nmax];
deque<int> dek;
bool vis[nmax];
int k;
void dfs(int u, int p = 0) {
  depth[u] = depth[p] + 1;
  dek.push_back(u);
  for (int v : g[u])
    if (v != p) {
      if (depth[v]) {
        if (p == 0) continue;
        int d = depth[u] - depth[v] + 1;
        if (d <= k and d > 0) {
          cout << "2\n";
          while (dek.front() != v) dek.pop_front();
          cout << dek.size() << "\n";
          for (int x : dek) cout << x << " ";
          exit(0);
        }
      } else
        dfs(v, u);
    }
  dek.pop_back();
}
int deg[nmax];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  while (true) {
    for (int i = 1; i <= n; i++)
      shuffle(g[i].begin(), g[i].end(), rng), vis[i] = 0, depth[i] = 0;
    dfs(rng() % n + 1);
    priority_queue<pair<pair<int, int>, int> > pq;
    for (int i = 1; i <= n; i++) deg[i] = g[i].size();
    for (int i = 1; i <= n; i++) pq.push({{-deg[i], rng()}, i});
    vector<int> ans;
    while (pq.size()) {
      auto z = pq.top();
      pq.pop();
      int u = z.second;
      if (vis[u]) continue;
      vis[u] = true;
      ans.push_back(u);
      if (ans.size() == (k + 1) / 2) {
        cout << "1\n";
        for (int x : ans) cout << x << " ";
        exit(0);
      }
      for (int v : g[u])
        if (!vis[v]) {
          vis[v] = true;
          for (int vv : g[v])
            if (!vis[vv]) {
              deg[vv]--;
              pq.push({{-deg[vv], rng()}, vv});
            }
        }
    }
  }
}
