#include <bits/stdc++.h>   using namespace std;   using int64 = long long;   using pii = pair<int, int>;   using vchar = vector<char>;   using vvchar = vector<vchar>;   using vint = vector<int>;   using vint64 = vector<int64>;   using vvint = vector<vint>;   using vbool = vector<bool>;   using vpii = vector<pii>;   template <typename T>   T sqr(T x) {     return x * x;   }   template <typename T>   T gcd(T a, T b) {     return b == 0 ? a : gcd(b, a % b);   }   pair<int, vint> solveD(vvint g, int k) {     enum { NOT_VISITED, STARTED, FINISHED };     const int n = g.size();     vint depth(n, -1);     depth[0] = 0;     vint parent(n, -1);     vint loopState(n, NOT_VISITED);     pair<int, vint> result;     result.first = 0;     std::function<void(int)> DFS = [&](int v) {       loopState[v] = STARTED;       const int previous = parent[v];       if (result.first != 0) return;       int backVertex = -1;       int backDepth = -1;       for (auto to : g[v]) {         if (to == previous) continue;         if (loopState[to] == STARTED && depth[to] > backDepth) {           backVertex = to;           backDepth = depth[to];         }       }       if (backVertex != -1) {         vint loop;         for (int u = v; u != backVertex; u = parent[u]) {           loop.push_back(u);         }         loop.push_back(backVertex);         reverse(std::begin(loop), std::end(loop));         assert(depth[v] - depth[backVertex] + 1 == loop.size());         const int loopLength = loop.size();         if (loopLength > k) {           result.first = 1;           for (int i = 0; i < loop.size(); i += 2) {             result.second.push_back(loop[i]);           }           result.second.resize((k + 1) / 2);         } else {           result.first = 2;           result.second = loop;         }         return;       }       for (auto to : g[v]) {         if (loopState[to] == NOT_VISITED) {           parent[to] = v;           depth[to] = depth[v] + 1;           DFS(to);           if (result.first != 0) return;         }       }       loopState[v] = FINISHED;     };     DFS(0);     if (result.first != 0) {       return result;     }     vint colors(n, -1);     std::function<void(int, int)> biColor = [&](int v, int color) {       colors[v] = color;       for (auto to : g[v]) {         if (colors[to] == -1) {           biColor(to, 1 - color);         }       }     };     biColor(0, 0);     int colorCount[2] = {0};     for (int i = 0; i < n; ++i) {       colorCount[colors[i]]++;     }     const int bestColor = colorCount[0] > colorCount[1] ? 0 : 1;     result.first = 1;     for (int i = 0; i < n; ++i) {       if (colors[i] == bestColor) {         result.second.push_back(i);       }     }     result.second.resize((k + 1) / 2);     return result;   }   int main() {     int T = 1;     std::ios::sync_with_stdio(false);     while (T--) {       int n;       cin >> n;       ;       int m;       cin >> m;       ;       int k;       cin >> k;       ;       vvint g(n);       while (m--) {         int u;         cin >> u;         ;         int v;         cin >> v;         ;         u--, v--;         g[u].push_back(v);         g[v].push_back(u);       }       auto result = solveD(g, k);       assert(result.first == 1 || result.first == 2);       cout << result.first << endl;       for (int& v : result.second) {         v++;       }       if (result.first == 2) {         cout << result.second.size() << endl;       }       std::copy(std::begin(result.second), std::end(result.second),                 ostream_iterator<int>(cout,    ));       cout << endl;     }     return 0;   }   