#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <chrono>
#include <random>
#include <numeric>
#include <set>
#include <deque>
#include <stack>
#include <sstream>
#include <utility>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m; cin >> n >> m;
    vector<vector<int>> g(n);
    for(int i=0;i<m;i++){
        int x,y; cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int rem=n;
    int chi=0;
    vector<int> mo,c1,c2;
    vector<int> used(n);
    vector<int> visited(n);
    auto dfs=[&](auto dfs,int s,int p)->void{
        if(rem != c1.size() and !visited[s]){
            mo.push_back(s);
            used[s] = 1;
            rem--;
        }
        visited[s] = 1;
        for(int t:g[s]){
            if(visited[t])continue;
            dfs(dfs,t,s);
            if(rem != c1.size()){
                assert(mo.back() == t); // になってるはず……
                mo.pop_back();
                c1.push_back(t);
            }
        }
    };
    dfs(dfs,0,-1);
    cout << mo.size() << " " << (n - mo.size())/2 << "\n";
    for(int i=0;i<n;i++){
        if(!used[i]){
            c2.push_back(i);
        }
    }
    for(int i:mo){
        cout << i+1 << " ";
    }
    cout << "\n";
    for(int i:c1){
        cout << i+1 << " ";
    }
    cout << "\n";
    for(int i:c2){
        cout << i+1 << " ";
    }
    cout << "\n";
}