#include <bits/stdc++.h>
#define N 10005
using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
int n,n1,n2,m,cuplaj;
vector<int>g[N],S[N],D[N];
int st[N],dr[N];
bitset<N>viz;
bool pair_up(int x)
{
    if(viz[x]) return 0;
    viz[x]=1;
    for(auto i:g[x])
        if(!dr[i])
    {
        st[x]=i;dr[i]=x;
        return 1;
    }
    for(auto i:g[x])
        if(pair_up(dr[i]))
    {
        st[x]=i;dr[i]=x;
        return 1;
    }
    return 0;
}
bool vizS[N],vizD[N];
void DFS(int x,bool ok)
{
    if(!ok)
    {
        vizS[x]=1;
        for(auto i:S[x])
            if(!vizD[i]) DFS(i,1);
    }
    else
    {
        vizD[x]=1;
        for(auto i:D[x])
            if(!vizS[i] &&dr[i]) DFS(i,0);
    }
}
int main()
{
    int i,x,y;
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y;
        g[x].push_back(y);
        S[x].push_back(y);D[y].push_back(x);
    }
    bool ok=1;
    n1=n2=n;
    while(ok)
    {
        ok=0;viz.reset();
        for(int i=1;i<=n1;i++)
            if(!st[i]) ok|=pair_up(i);
    }
    for(int i=1;i<=n1;i++) cuplaj+=!!st[i];
    fout<<2*n-cuplaj<<"\n";
    ///for(int i=1;i<=n1;i++)
       /// if(st[i]) fout<<i<<" "<<st[i]<<"\n";
    for(i=1;i<=n;i++)
        if(!st[i]&&!vizS[i]) DFS(i,0);
    for(i=1;i<=n;i++) cout<<vizS[i]<<" ";cout<<"\n";
    for(i=1;i<=n;i++) cout<<vizD[i]<<" ";cout<<"\n";
    ///K=(A/Z)U(B&Z)=>vizS[i]=0&&vizD[i]=1
    for(i=1;i<=n;i++)
        if(!vizS[i]&&vizD[i]) fout<<"0\n";
        else if(vizS[i]&&vizD[i]) fout<<"1\n";
        else if(!vizS[i]&&!vizD[i]) fout<<"2\n";
        else fout<<"3\n";
    return 0;
}