#include<iostream>
#include<set>
#include<vector>
using namespace std;
vector<pair<int,bool> >e[100005];
bool vis[100005];
int sd[100005]={0,1};
set<int>st[100005];
int sdmax=0;
int fa[100005]={0,0};
void dfs(int x){
//	cout << x << " ";
	vis[x]=1;
	st[sd[x]].insert(x);
	for(int i=0;i<e[x].size();i++){
		if(vis[e[x][i].first]==0){
			e[x][i].second=1;
			
			int tempp=e[x][i].first;
			for(int j=0;j<e[tempp].size();j++){
				if(e[tempp][j].first==x){
					e[tempp][j].second=1;
				}
			} 
			
			sd[e[x][i].first]=sd[x]+1;
			sdmax=max(sdmax,sd[x]+1);
			fa[e[x][i].first]=x;
			dfs(e[x][i].first);
		}
	}
}
int tmp[100005];
int n,m,k;
void solve2(int i,int j,int sizeH){
//	cout << e[i][j].first << " " << i << endl;
	cout << 2 << endl;
	int cntt=0;
	int xx=i;
	while(1){
//		cout << "DEBUG:" << xx << " "; 
		tmp[++cntt]=xx;
		xx=fa[xx];
		if(xx==e[i][j].first){
			tmp[++cntt]=xx;
			break;
		}
	}
	cout << sizeH << endl;
	for(int g=cntt;g>=1;g--){
			cout << tmp[g] << " ";
	}
}
bool check1(int q,int& h,int& xb,int& sizeH){
	int ans1=q,ans2=h,ans3=xb;
	int x=h;
	for(int i=x;sd[i]>sd[q];i=fa[i]){
		for(int j=0;j<e[i].size();j++){
			if(sd[e[i][j].first]<sd[i]&&e[i][j].second==0&&sd[e[i][j].first]>sd[q]&&sd[i]-sd[e[i][j].first]+1<=sizeH){
//				cout << "IN CHECK1 NQ-H:" << " " << e[i][j].first << " " << i << endl; 
				ans1=e[i][j].first;ans2=i;ans3=j;
				h=ans2;xb=ans3;
				sizeH=sd[i]-sd[e[i][j].first]+1;
			}
		} 
	}
	h=ans2;xb=ans3;
//	cout << "CHECK1 END:" << e[h][xb].first << " " << h << " " << sizeH << endl;
	return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k;
	for(int i=1;i<=m;i++){
		int u,v;
		cin >> u >> v;
		pair<int,bool>x;
		x.first=v;x.second=0;
		e[u].push_back(x);
		x.first=u;
		e[v].push_back(x);
	}
//	cout << "DFSTREE:";
	dfs(1);
//	cout << endl;
	for(int i=1;i<=n;i++){
		for(int j=0;j<e[i].size();j++){
//			cout << i << " " << e[i][j].first << " " << e[i][j].second << endl;
			if(e[i][j].second==0&&sd[e[i][j].first]<sd[i]){
//				cout << i << " " << e[i][j].first << endl;
				int sizeH=sd[i]-sd[e[i][j].first]+1;
				check1(e[i][j].first,i,j,sizeH); //内置小环 
				//有环
				if(sizeH<=k){
//					//环小 直出2 
					solve2(i,j,sizeH);
					return 0;
				}
				else {
					//环大
					int xx=i;
					cout << 1 << endl;
					int lim=(k+1)/2;
					for(int l=1;l<=lim;l++){
						cout << xx << " ";
						xx=fa[xx];xx=fa[xx];
					} 
					return 0;
				}
			}
		}
	}
//	cout << sdmax << " ";
//	for(int i=1;i<=n;i++){
//		cout << sd[i] << " "; 
//	}
//	cout << endl;
	int cnt=0;
	cout << 1 << endl;
	for(int i=1;i<=sdmax;i+=2){
		for(set<int>::iterator it=st[i].begin();it!=st[i].end();it++){
			int tmpp=*it;
			cout << tmpp << " ";
			cnt++;
			if(cnt==(k+1)/2){
				return 0;
			}
		}
	}
//	cout << "RENJI";
	return 0;
}