rt，被卡掉了，独立集但是输出了相邻点。

#include <iostream>
#include <stack>
#include <cmath>
#include <vector>
#include <map>
#include <string.h>
#include <queue>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#define int long long
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using namespace std;
const int N = 4e5 + 10;
const int INF = 0x3f3f3f3f;
bool Mbe;
int n, m, k;
int head[N], ne[N], to[N], id;
void add(int x, int y)
{
	to[++id] = y;
	ne[id] = head[x];
	head[x] = id;
}
int dep[N];
int md = 1e9;//max dep
int s, e;
int fa[N];
bool vis[N];
void dfs(int u, int faa)
{
	dep[u] = dep[faa] + 1;
	fa[u] = faa;
	vis[u] = 1;
	for(int i = head[u]; i; i = ne[i])
	{
		int v = to[i];
		if(v == faa) continue;
		if(vis[v])
		{
			if(dep[v] < dep[u] && dep[u] - dep[u] + 1 < md)
			{
				md = dep[u] - dep[v] + 1;
				s = u;
				e = v;
			}
			continue;
		}
		dfs(v, u);
	}
}
void tree()
{
	cout << 1 << "\n";
	int cnt = 0;
	for(int i = 1; i <= n; i++)
	{
		cnt += (dep[i] & 1);
	}
	int f = 1;
	if(cnt < k / 2) f = 0;
	int ct = 0;
	for(int i = 1; i <= n; i++)
	{
		if(dep[i] % 2 == f)
		{
			cout << i << " ";
			ct++;
		}
		if(ct == (k + 1) / 2) break;
	}
	cout << "\n";
}

bool Med;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		add(x, y);
		add(y, x);
	}
	dfs(1, 0);
	if(m == n - 1)
	{
		tree();
		exit(0);
	}
	if(md <= k)
	{
		cout << 2 << "\n";
		cout << md << "\n";
		for(int i = s; i != e && i != 0; i = fa[i])
		{
			cout << i << " ";	
		}
		cout << e << "\n";
		exit(0);
	}
	cout << 1 << "\n";
	int cnt = 0;
	for( ; s != fa[e] && s != fa[fa[e]] ; s = fa[fa[s]])
	{
		cout << s << " ";
		cnt++;
		if(cnt == (k + 1) / 2) break;
	}
	return 0;
}