#include<fstream>
#include<iostream>
#include<vector>
#define DN 8205
#define pb push_back
using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
int n,m,f,g,c1[DN],c2[DN],p,viz[DN],nr,st[4*DN],top,poz1,poz2;
int rez[4*DN];
vector<int>v[4*DN];
vector<int>r[4*DN];
void ve2(int f,int g)
{
    int f2,g2;
    f2=-f+2*n;
    g2=-g+2*n;
    f+=2*n;
    g+=2*n;
    r[f2].pb(g);
    r[g2].pb(f);
}
int ve1(int nod)
{
    if(viz[nod])
        return 0;
    viz[nod]=1;
    for(auto i:v[nod])
        if(!c2[i])
        {
            c1[nod]=i;
            c2[i]=nod;
            return 1;
        }
    for(auto i:v[nod])
        if(c2[i]!=nod&&ve1(c2[i]))
        {
            c1[nod]=i;
            c2[i]=nod;
            return 1;
        }
    return 0;
}
void dfs(int nod)
{
    viz[nod]=2;
    for(auto i:v[nod])
        if(viz[i]!=2)
            dfs(i);
    top++;
    st[top]=nod-2*n;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>f>>g;
        v[f].pb(g);
        ve2(f,g+n);
    }
    p=1;
    while(p)
    {
        p=0;
        for(int i=1;i<=n;i++)
            viz[i]=0;
        for(int i=1;i<=n;i++)
            if(c1[i]==0&&ve1(i))
            {
                nr++;
                p=1;
            }
    }
    cout<<nr<<'\n';
    for(int i=1;i<=n;i++)
        if(c1[i])
            cout<<i<<' '<<c1[i]<<'\n';
    for(int i=1;i<=n;i++)
        if(c1[i])
            ve2(-i,-c1[i]-n);
    fout<<2*n-nr<<'\n';
    for(int i=0;i<=4*n;i++)
        if(viz[i]!=2)
            dfs(i);
    for(int i=top;i>=1;i--)
    {
        poz1=st[i]+2*n;
        poz2=-st[i]+2*n;
        if(!rez[poz1]&&!rez[poz2])
            rez[poz2]=1;
    }
    for(int i=1;i<=n;i++)
    {
        poz1=i+2*n;
        poz2=n+i+2*n;
        if(!rez[poz1]&&!rez[poz2])
        {
            fout<<3<<'\n';
            continue;
        }
        if(!rez[poz1])
        {
            fout<<1<<'\n';
            continue;
        }
        if(!rez[poz2])
        {
            fout<<2<<'\n';
            continue;
        }
        fout<<0<<'\n';
    }
}