思路是先找到一个环，然后遍历所有边，如果两个端点都在环内（即将环分成两半），就选较小的环分割；则环大小每次至少减半，次数不超过 $\log n$，总复杂度 $n+m\log n$。但是 WA#17，求调/求证伪/kel

具体使用 vector 实现。

#include <bits/stdc++.h>
#define int long long
#define fs first
#define sc second

using namespace std;

const int maxn = 1e6 + 10;
typedef pair<int, int> pii;

int n, m, k;
pii e[maxn];
vector<pii> g[maxn];
vector<int> r;
int pos[maxn];
int vis[maxn];
bool fl = 0;
stack<int> st;
int col[maxn];
int cnt[2];

void dfs(int u, int fa, int c) {
	vis[u] = 1;
	cnt[col[u] = c]++;
	st.push(u);
	for (pii ele : g[u]) {
		int v = ele.fs;
		if (ele.sc == fa) continue;
		if (vis[v] && !fl) {
			int p;
			do {
				r.push_back(p = st.top());
				st.pop();
			} while (p != v);
			fl = 1;
		} else dfs(v, ele.sc, c ^ 1);
		if (fl) return;
	}
}

signed main() {
	cin >> n >> m >> k;
	for (int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		g[u].push_back({v, i});
		g[v].push_back({u, i});
		e[i] = {u, v};
	}
	dfs(1, 0, 0);
	if (!fl) {
		int c = cnt[1] > cnt[0];
		int z = (k + 1) >> 1;
		cout << 1 << endl;
		for (int i = 1; i <= n; i++) {
			if (z && col[i] == c) {
				cout << i << " ";
				z--;
			}
		}
		return 0;
	}
	while (true) {
		bool f = 0;
		memset(pos, -1, sizeof(pos));
		int w = r.size();
		for (int i = 0; i < w; i++) pos[r[i]] = i;
		for (int i = 1; i <= m; i++) {
			int u = e[i].fs, v = e[i].sc;
			if (pos[u] != -1 && pos[v] != -1) {
				int pu = pos[u], pv = pos[v];
				if ((pu + 1) % w == pv || (pv + 1) % w == pu) continue;
				f = 1;
				if (pu > pv) swap(u, v), swap(pu, pv);
				int l1 = pv - pu - 1, l2 = w - l1 - 2;
				if (l1 < l2) {
					vector<int> r_;
					for (int i = 0; i < w; i++) {
						if (i >= pu && i <= pv) r_.push_back(r[i]);
					}
					r.swap(r_);
				} else {
					vector<int> r_;
					for (int i = 0; i < w; i++) {
						if (i <= pu || i >= pv) r_.push_back(r[i]);
					}
					r.swap(r_);
				}
				break;
			}
		}
		if (!f) break;
	}
	if (r.size() <= k) {
		cout << 2 << endl;
		cout << r.size() << endl;
		for (int i : r) cout << i << " ";
	} else {
		cout << 1 << endl;
		int z = (k + 1) >> 1;
		for (int i = 0; i < r.size(); i += 2) {
			if (z) {
				cout << r[i] << " ";
				z--;
			}
		}
	}
	return 0;
}