//什么时候我才能有杜爷一半强啊/kk
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=200086;
int n,m,tot,tp,st[N],sze[N],hs[N],h[N],a,b;
bool vis[N];
struct edge{int v,nxt;}e[N<<1];
vector<int>vec[N],mem[2];
int read(){
	char ch=getchar();int nn=0,ssss=1;
	while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
	return nn*ssss;
}
bool add(int u,int v){e[++tot].v=v;e[tot].nxt=h[u];h[u]=tot;return true;}
int build(int np){
	sze[np]=1;vis[np]=true;
	for(int i=h[np];i;i=e[i].nxt){
		if(vis[e[i].v])continue;
		sze[np]+=build(e[i].v);vec[np].push_back(e[i].v);
		if(sze[e[i].v]>sze[hs[np]])hs[np]=e[i].v;
	}
	return sze[np];
}
bool Merge(int np,int S){
	mem[S].push_back(np);
	for(vector<int>::iterator it=vec[np].begin();it!=vec[np].end();it++)Merge(*it,S);
	return true;
}
bool dfs(int np){
	sort(vec[np].begin(),vec[np].end(),[](int a,int b){return sze[a]<sze[b];});
	st[++tp]=np;//printf("dfs %d %d\n",np,hs[np]);
	for(vector<int>::iterator it=vec[np].begin();it!=vec[np].end();it++){
		if((*it)==hs[np])continue;
		//printf("v %d %d\n",np,*it);
		if(a<b)a+=sze[*it],Merge(*it,0);
		else b+=sze[*it],Merge(*it,1);
	}
	//printf("np : %d , %d %d\n",np,a,b);
	if(a+sze[hs[np]]==b&&hs[np]){a+=sze[hs[np]];return Merge(hs[np],0);}
	if(b+sze[hs[np]]==a&&hs[np]){b+=sze[hs[np]];return Merge(hs[np],1);}
	return hs[np]?dfs(hs[np]):true;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=m;i++){
		int u=read();int v=read();
		add(u,v);add(v,u);
	}
	build(1);dfs(1);
	printf("%d %d\n",tp,a);
	for(int i=1;i<=tp;i++)printf("%d ",st[i]);puts("");
	for(vector<int>::iterator it=mem[0].begin();it!=mem[0].end();it++)printf("%d ",*it);puts("");
	for(vector<int>::iterator it=mem[1].begin();it!=mem[1].end();it++)printf("%d ",*it);
}