#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream in("felinare.in");
ofstream out("felinare.out");
vector< vector<int> > a;
vector<int> gr1,gr2;
vector<bool> v,lf,rt;
int n,m;
//........................
int pairup(int x)
{
    if(v[x])return 0;
    v[x]=true;
    for(auto i: a[x])
        if(gr2[i]==0)
        {
            gr1[x]=i;
            gr2[i]=x;
            lf[x]=true;
            return 1;
        }
     for(auto i: a[x])
        if(pairup(gr2[i]))
        {
            gr1[x]=i;
            gr2[i]=x;
            lf[x]=true;
            return 1;
        }
    return 0;
}
//.......................
void suport(int x)
{
    for(auto i: a[x])
        if(rt[i]==false)
        {
            rt[i]=true;
            lf[gr2[i]]=false;
            suport(gr2[i]);
        }
}
//....................
int main()
{
    in>>n>>m;
    a=vector< vector<int> > (n+1);
    gr1=gr2=vector<int> (n+1);
    lf=rt=vector<bool> (n+1);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        in>>x>>y;
        a[x].pb(y);
    }
    //...................
    for(int step=1;step;)
    {
        step=0;
        v=vector<bool> (n+1);
        for(int i=1;i<=n;i++)
            if(gr1[i]==0)
            step+=pairup(i);
    }
    //....................
    int cnt=2*n;
    for(int i=1;i<=n;i++)
        if(gr1[i])
        cnt--;
    out<<cnt<<'\n';

    for(int i=1;i<=n;i++)
        if(lf[i]==false)
        suport(i);

    for(int i=1;i<=n;i++)
        if(lf[i] && rt[i])out<<0<<'\n';
        else if(rt[i])out<<1<<'\n';
        else if(lf[i])out<<2<<'\n';
        else out<<3<<'\n';

    return 0;
}