// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF=1e12;

struct node{
    int to,cap,flow,cost,rev;
};

vector<vector<node>> v;
vector<int> d,re,pn,pe;

void NE(int U,int V,int cap,int cost){
    v[U].push_back({V,cap,0,cost,v[V].size()});
    v[V].push_back({U,0,0,-cost,v[U].size()-1});
}

void spfa(int s) {
    //https://cp-algorithms.com/graph/bellman_ford.html
    //W copy paste
    int n = v.size();
    d.assign(n, INF);
    pe.assign(n, -1);
    pn.assign(n, -1);
    vector<int> cnt(n, 0);
    vector<bool> inqueue(n, false);
    queue<int> q;
    d[s] = 0;
    q.push(s);
    inqueue[s] = true;
    while (!q.empty()) {
        int a = q.front();
        q.pop();
        inqueue[a] = false;
        for(int i = 0;i<v[a].size();i++){
            node &edge=v[a][i];
            if(edge.cap-edge.flow>0&&d[a]+edge.cost<d[edge.to]){
                d[edge.to]=d[a]+edge.cost;
                pn[edge.to]=a;
                pe[edge.to]=i;
                if(!inqueue[edge.to]){
                    q.push(edge.to);
                    inqueue[edge.to]=true;
                }
            }
        }
    }
}

signed main() {
    int n,m;cin>>n>>m;
    v.resize(2*n+3);
    vector<int> volte(n+1),kivolt(n+1);
    for(int i = 0;i<m;i++){
        int U,V;cin>>U>>V;
        NE(U*2+1,V*2,2,0);
        volte[V]=1;
        kivolt[U]=1;
    }
    for(int i = 1;i<=n;i++){
        NE(i*2,i*2+1,1,-1);
        NE(i*2,i*2+1,1,0);
        if(!kivolt[i])NE(i*2+1,2*(n+1),2,0);
        if(!volte[i])NE(0,i*2,2,0);
    }
    spfa(0);
    int hanyan=-d[2*(n+1)];
    int curi=2*n+2; //W old spice
    while(curi!=0){
        int prn=pn[curi],pre=pe[curi],revi=v[prn][pre].rev;
        v[prn][pre].flow++;
        v[curi][revi].flow--;
        curi=prn;
    }
    //W copy paste
    spfa(0);
    hanyan+=-d[2*(n+1)];
    curi=2*n+2;
    while(curi!=0){
        int prn=pn[curi],pre=pe[curi],revi=v[prn][pre].rev;
        v[prn][pre].flow++;
        v[curi][revi].flow--;
        curi=prn;
    }
    cout<<hanyan<<endl;
    vector<int> ans1;
    curi=0;
    while(curi!=n*2+2){
        for(node &e : v[curi]){
            if(e.flow>0){
                e.flow--;
                if(curi%2==0&&curi>0&&curi<n*2+2)ans1.push_back(curi/2);
                curi=e.to;
                break;
            }
        }
    }
    ans1.push_back(0);
    for(int i : ans1)cout<<i<<' ';
    cout<<endl;
    //W copy paste
    vector<int> ans2;
    curi=0;
    while(curi!=n*2+2){
        for(node &e : v[curi]){
            if(e.flow>0){
                e.flow--;
                if(curi%2==0&&curi>0&&curi<n*2+2)ans2.push_back(curi/2);
                curi=e.to;
                break;
            }
        }
    }
    ans2.push_back(0);
    for(int i : ans2)cout<<i<<' ';
    cout<<endl;
}