#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define For(i,x,y) for(int i=(int)(x);i<=(int)(y);++i)
#define Rof(i,x,y) for(int i=(int)(x);i>=(int)(y);--i)
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)<(y)?(y):(x))
#define chkmin(x,y) x=min((x),(y))
#define chkmax(x,y) x=max((x),(y))
#define DEBUG 1
namespace FastIO{
#define isdigit(x) (x>='0'&&x<='9')
#define MAXSIZE (1<<20)
#define PREC 6
#define FileIO(fn) freopen(fn".in","r",stdin),freopen(fn".out","w",stdout)
	char buf[MAXSIZE],pbuf[MAXSIZE],*pp=pbuf,*p1,*p2;
	struct CONDES{
#if DEBUG
#else
		CONDES(){p1=buf;p2=buf;pp=pbuf;}
		~CONDES(){fwrite(pbuf,1,pp-pbuf,stdout);}
#endif
	}_CONDES;
	inline char gc(){
#if DEBUG
		return getchar();
#endif
		if(p1==p2)p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin);
		return p1==p2?' ':*p1++;
	}
	template<class T>
	inline void read(T&x){
		double tmp=1;
		bool sign=0;x=0;
		char c=gc();
		for(;!isdigit(c);c=gc())if(c=='-')sign=1;
		for(;isdigit(c);c=gc())x=x*10+(c-'0');
		if(c=='.')for(c= gc();isdigit(c);c=gc())tmp/=10.0,x+=tmp*(c-'0');
		if(sign)x=-x;
	}
	inline bool blank(char ch){
		return ch==' '||ch=='\n'||ch=='\r'||ch=='\t'||ch==EOF;
	}
	inline void read(char *s){
		char c=gc();
		for(;blank(c);c=gc());
		for(;!blank(c);c=gc())*s++=c;
		*s=0;
	}
	inline void read(char &c){for(c=gc();blank(c);c=gc());}
	template<class T,class...Args>
	inline void read(T&x,Args&...args){read(x);read(args...);}
	inline void pc(const char &c){
#if DEBUG
		putchar(c);
#else
		if(pp-pbuf==MAXSIZE)fwrite(pbuf,1,MAXSIZE,stdout),pp=pbuf;
		*pp++=c;
#endif
	}
	template<class T>
	inline void write(T x){
		if(x<0)x=-x,pc('-');
		static int sta[35];
		int top=0;
		do{sta[top++]=x%10,x/=10;}while(x);
		while(top)pc(sta[--top]+'0');
	}
	inline void write(char* s){while(*s)pc(*s++);}
	inline void write(const char* s){while(*s)pc(*s++);}
	inline void write(char c){pc(c);}
	template<class T>
	inline void write_float(T x,int prec=PREC){
		if(x==0){pc('0');pc('.');while(prec--)pc('0');return;}
		if(x<0)x=-x,pc('-');
		static int sta[35];
		int top=0;T pw=pow(10,prec);
		x=round(pw*x);
		if(x<pw)pc('0'),pc('.');
		do{sta[top++]=((ull)x)%10;x=x/10.0;}while(x>=1.0||top<prec);
		while(top){pc(sta[--top]+'0');if(top==prec)pc('.');}
	}
	inline void write(float x){write_float(x);}
	inline void write(double x){write_float(x);}
	inline void write(long double x){write_float(x);}
	template<class T,class...Args>
	inline void write(T x,Args...args){write(x);write(args...);}
};
using namespace FastIO;
const int N=1e5+5;
struct edge{int to,nx;}e[N<<2];
int n,m,k,hd[N],dep[N],st[N],ec=0,cnt=0;
bool vs[N];
inline void added(int x,int y){
    e[++ec]={y,hd[x]};
	hd[x]=ec;
}
void dfs(int x,int fa){
	int i,y;
	vs[x]=1;st[dep[x]]=x;
	if(dep[x]&1)cnt++;
	for(i=hd[x];i;i=e[i].nx){
		y=e[i].to;
		if(y==fa)continue;
		if(vs[y]){
			int s=dep[x]-dep[y]+1,j,t;
			if(s<=k){
				write("2\n",s,'\n');
				for(j=dep[y];j<=dep[x];j++)write(st[j],' ');
			}else{
				write("1\n");
				for(j=dep[y],t=1;t<=k+1>>1;j+=2,t++)write(st[j],' ');
			}
			exit(0);
		}
		dep[y]=dep[x]+1;
		dfs(y,x);
	}
}
signed main(){
	int i,j,x,y;
	read(n,m,k);
	for(i=1;i<=m;i++){
		read(x,y);
		added(x,y);
		added(y,x);
	}
	dep[1]=1;
	dfs(1,0);
	write("1\n");
	for(i=1,j=1;i<=n&&j<=k+1>>1;i++)
		if(dep[i]&1==(cnt>=(k+1>>1))?1:0)
			write(i,' '),j++;
	return 0;
}

WA on 49