#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn = 200005;
vector<vector<int>>g(mxn);
vector<vector<int>>adj(mxn);
vector<bool>vis(mxn);
vector<int>sz(mxn);
set<int>leftv;
vector<int>ans;
int rq = 0;
void dfs(int u){
	sz[u] = 1;
	for(int nxt: adj[u]){
		if(vis[nxt])continue;
		g[u].push_back(nxt);
		vis[nxt] = true;
		dfs(nxt);
		sz[u]+=sz[nxt];
	}
}
set<int> get(int u, int p){
	set<int>s;
	s.insert(u);
	for(int nxt: g[u]){
		set<int>t = get(nxt,u);
		if(s.size()<t.size()){
			swap(s,t);
		}
		for(int nxt: t){
			s.insert(nxt);
		}
	}
	return s;
}
void dfs1(int u, int p){
	if(rq == sz[u]*2){
		for(int nxt: get(u, p)){
			leftv.insert(nxt);
		}
		return;
	}
	rq--;
	ans.push_back(u);
	vector<pair<int,int>>vals;
	for(int nxt: g[u]){
		vals.push_back({sz[nxt],nxt});
	}
	if(rq==0){
		return;
	}
	sort(vals.begin(),vals.end());
	for(auto [_, nxt]: vals){
		if(rq >= sz[nxt]*2){
			//cout << "found " << '\n';
			rq-=sz[nxt]*2;
			for(int node: get(nxt, p)){
				//cout << "get " << nxt << '\n';
				leftv.insert(node);
			}
			if(rq==0)return;
			continue;
		}
		dfs1(nxt, u);
		return;
	}
}
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	vis[1] = true;
	int n,m;
	cin >> n >> m;
	for(int i = 0; i<m; i++){
		int x,y;
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	rq = n;
	dfs(1);
	dfs1(1,0);
	cout << ans.size() << ' ' << (n-ans.size())/2 << '\n';
	set<int>right;
	for(int i = 1; i<=n; i++){
		right.insert(i);
	}
	for(int i = 0; i<ans.size(); i++){
		right.erase(ans[i]);
		cout << ans[i];
		if(i+1<ans.size())cout << ' ';
	}
	for(int nxt: leftv){
		right.erase(nxt);
	}
	cout << '\n';
	assert(leftv.size() == right.size());
	if((n-ans.size())/2){
		vector<int>vec;
		for(int nxt: leftv){
			vec.push_back(nxt);
		}
		for(int i = 0; i<vec.size(); i++){
			cout << vec[i];
			if(i+1<vec.size())cout << ' ';
		}
		cout << '\n';
		vec.clear();
		for(int nxt: right){
			vec.push_back(nxt);
		}
		for(int i = 0; i<vec.size(); i++){
			cout << vec[i];
			if(i+1<vec.size())cout << ' ';
		}
		cout << '\n';
	}
	return 0;
}