#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
template <typename A>
ostream &operator<<(ostream &cout, vector<A> const &v);
template <typename A, typename B>
ostream &operator<<(ostream &cout, pair<A, B> const &p) {
  return cout << "(" << p.first << ", " << p.second << ")";
}
template <typename A>
ostream &operator<<(ostream &cout, vector<A> const &v) {
  cout << "[";
  for (int i = 0; i < v.size(); i++) {
    if (i) cout << ", ";
    cout << v[i];
  }
  return cout << "]";
}
template <typename A, typename B>
istream &operator>>(istream &cin, pair<A, B> &p) {
  cin >> p.first;
  return cin >> p.second;
}
mt19937 rng(steady_clock::now().time_since_epoch().count());
void usaco(string filename) {
  freopen((filename + ".in").c_str(), "r", stdin);
  freopen((filename + ".out").c_str(), "w", stdout);
}
const long double pi = 3.14159265358979323846;
const long long mod = 1000000007;
long long n, m, k, q, Q, T, l, r, x, y, z;
long long a[1000005];
long long b[1000005];
long long c[1000005];
string second, t;
long long ans = 0;
long long sq;
set<pair<int, int> > degs;
vector<int> edges[200005];
long long deg[100005];
bool vis[100005];
bool anc[100005];
long long dep[100005];
int targ = -1;
vector<int> nseq;
void dfs(int v, int p, int d) {
  if (vis[v]) {
    if (anc[v] && dep[p] - dep[v] + 1 >= sq) {
      targ = v;
    }
    return;
  }
  dep[v] = d;
  vis[v] = 1;
  anc[v] = 1;
  for (int x : edges[v]) {
    dfs(x, v, d + 1);
    if (targ != -1) {
      nseq.push_back(v + 1);
      if (v == targ) {
        cout << 2 << endl;
        cout << nseq.size() << endl;
        {
          for (int ele = 0; ele < nseq.size(); ele++) {
            if (ele) cout << " ";
            cout << nseq[ele];
          }
          cout << '\n';
        };
        exit(0);
      }
      return;
    }
  }
  anc[v] = 0;
}
int main() {
  {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
  };
  cin >> n >> m;
  sq = ceil(sqrt(n)) + 1e-7;
  for (long long i = 0; i < (m); i++) {
    cin >> x >> y;
    --x;
    --y;
    edges[x].push_back(y);
    edges[y].push_back(x);
    ++deg[x];
    ++deg[y];
  }
  bool t1 = 1;
  if (t1) {
    for (long long i = 0; i < (n); i++) degs.insert(make_pair(deg[i], i));
    vector<int> qset;
    memset(vis, 0, sizeof(vis));
    while (degs.size()) {
      pair<int, int> v = *degs.begin();
      degs.erase(degs.begin());
      if (!vis[v.second]) {
        qset.push_back(v.second + 1);
        vis[v.second] = 1;
        for (int x : edges[v.second]) {
          if (!vis[x]) {
            vis[x] = 1;
            for (int y : edges[x]) {
              if (!vis[y]) {
                degs.erase(make_pair(deg[y], y));
                --deg[y];
                degs.insert(make_pair(deg[y], y));
              }
            }
          }
        }
      }
    }
    if (qset.size() >= sq) {
      cout << 1 << endl;
      {
        for (int ele = 0; ele < sq; ele++) {
          if (ele) cout << " ";
          cout << qset[ele];
        }
        cout << '\n';
      };
      exit(0);
    }
    if (n <= 16) {
      for (long long i = 0; i < ((1 << n)); i++) {
        bool v[n];
        memset(v, 0, sizeof(v));
        bool first = 1;
        for (long long j = 0; j < (n); j++) {
          if (i & (1 << j)) {
            if (v[j]) {
              first = 0;
              break;
            } else {
              v[j] = 1;
              for (int x : edges[j]) v[x] = 1;
            }
          }
        }
        int c = __builtin_popcount(i);
        if (first && c >= sq) {
          cout << 1 << endl;
          for (long long j = 0; j < (n); j++)
            if (c > 0 && (i & (1 << j))) {
              cout << j + 1 << " ";
              --c;
            }
          cout << endl;
          exit(0);
        }
      }
    }
  }
  iota(a, a + n, 0);
  for (long long i = 0; i < (n); i++) {
    int j = (rng() % (n - i)) + i;
    swap(a[i], a[j]);
  }
  for (long long i = 0; i < (n); i++) {
    for (long long j = 0; j < (n); j++) dep[j] = mod;
    memset(vis, 0, sizeof(vis));
    int v = a[i];
    dfs(v, -1, 0);
  }
}
