这是改之前，WA on#138，后来发现应该先找最小环

#include<bits/stdc++.h>
#define int long long
#define re register
using namespace std;
const int N=4e6+10;
int n,m,k,dep[N],h[N],fa[N];
int e[N],ne[N],id;
bool vis[N];
void add(int a,int b)
{
	e[++id]=b;
	ne[id]=h[a];
	h[a]=id;
}
void dfs(int u)
{
	vis[u]=1;
	dep[u]=dep[fa[u]]+1;
	for(int i=h[u];i;i=ne[i])
	{
		int v=e[i];
		if(v==fa[u])continue;
		if(vis[v])
		{
			if(dep[u]-dep[v]<k)
			{
				puts("2");
				printf("%lld\n",dep[u]-dep[v]+1);
				for(int j=u;j!=fa[v];j=fa[j])printf("%lld ",j);
				exit(0);
			}
			else
			{
				puts("1");
				for(int j=u,flag=1;flag<=k&&j!=fa[v];j=fa[j],flag++)if(flag&1)printf("%lld ",j);
				exit(0);
			}
		}
		else
		{
			fa[v]=u;
			dfs(v);
		}
	}
	vis[u]=0;
}
int num[2];
void dfs1(int u,bool flag=1)
{
	++num[flag];
	for(int i=h[u];i;i=ne[i])
	{
		int v=e[i];
		if(v==fa[u])continue;
		dfs1(v,flag^1);
	}
}
int tim;
void dfs2(int u,bool flag)
{
	if(flag)
	{
		printf("%lld ",u);
		++tim;
		if(tim==ceil(k/2.))exit(0);
	}
	for(int i=h[u];i;i=ne[i])
	{
		int v=e[i];
		if(v==fa[u])continue;
		dfs2(v,flag^1);
	}
}
signed main()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	int u,v;
	while(m--)
	{
		scanf("%lld%lld",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs(1);
	puts("1");
	dfs1(1);
	dfs2(1,num[1]>num[0]);
}

这是改完之后

#include<bits/stdc++.h>
#define re register
using namespace std;
const int N=4e6+10;
int n,m,k,dep[N],h[N],fa[N];
int e[N],ne[N],id;
bool vis[N];
void add(int a,int b)
{
	e[++id]=b;
	ne[id]=h[a];
	h[a]=id;
}
int x;
void dfs(int u)
{
	vis[u]=1;
	dep[u]=dep[fa[u]]+1;
	for(int i=h[u];i;i=ne[i])
	{
		int v=e[i];
		if(v==fa[u])continue;
		if(vis[v])
		{
			if(dep[u]-dep[v]<k)
			{
				puts("2");
				printf("%d\n",dep[u]-dep[v]+1);
				for(int j=u;j!=fa[v];j=fa[j])printf("%d ",j);
				exit(0);
			}
			else x=u;
		}
		else
		{
			fa[v]=u;
			dfs(v);
		}
	}
	vis[u]=0;
}
int num[2];
void dfs1(int u,bool flag=1)
{
	++num[flag];
	for(int i=h[u];i;i=ne[i])
	{
		int v=e[i];
		if(v==fa[u])continue;
		dfs1(v,flag^1);
	}
}
int tim;
void dfs2(int u,bool flag)
{
	if(flag)
	{
		printf("%d ",u);
		++tim;
		if(tim==ceil(k/2.))exit(0);
	}
	for(int i=h[u];i;i=ne[i])
	{
		int v=e[i];
		if(v==fa[u])continue;
		dfs2(v,flag^1);
	}
}
signed main()
{
	scanf("%d%d%d",&n,&m,&k);
	int u,v;
	while(m--)
	{
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs(1);
	if(x)
	{
		puts("1");
		for(int j=0;j<k;x=fa[fa[x]],j+=2)printf("%d ",x);
		exit(0);
	}
	puts("1");
	dfs1(1);
	dfs2(1,num[1]>num[0]);
}

改完就T了