#include <bits/stdc++.h>

using namespace std;
ifstream f("felinare.in");
ofstream g("felinare.out");
vector <int> v[8200];
int sel[8200],r[8200],l[8200],lin[8200],cmax,n,dr[8200],stg[8200];
int cupleaza (int node)
{
    int i,it;
    sel[node]=1;
    for (i=0;i<v[node].size();i++)
    {
        if (r[v[node][i]]==0)
        {
            l[node]=v[node][i];
            r[v[node][i]]=node;
            return 1;
        }
    }
    for (i=0;i<v[node].size();i++)
    {
        if (!sel[r[v[node][i]]]&&cupleaza(r[v[node][i]])!=0)
        {
            l[node]=v[node][i];
            r[v[node][i]]=node;
            return 1;
        }
    }
    return 0;
}
void solve ()
{
    int ok=1,i;
    while (ok==1)
    {
        ok=0;
        for (i=1;i<=n;i++)
        {
            sel[i]=0;
        }
        for (i=1;i<=n;i++)
        {
            if (l[i]==0&&sel[i]==0)
            {
                if (cupleaza(i)==1)
                {
                    cmax++;
                    ok=1;
                }
            }
        }
    }
}
void dfs (int node)
{
    int i,it;
    for (i=0;i<v[node].size();i++)
    {
        it=v[node][i];
        if (!dr[it])
        {
            dr[it]=1;
            lin[r[it]]=0;
            dfs(r[it]);
        }
    }
}
int i,nr,x,y;
int main()
{
    f>>n>>nr;
    for (i=1;i<=nr;i++)
    {
        f>>x>>y;
        v[x].push_back(y);
    }
    solve ();
    g<<2*n-cmax<<'\n';
    for (i=1;i<=n;i++)
    {
        if (l[i]!=0)
        {
            stg[i]=1;
        }
    }
    for (i=1;i<=n;i++)
    {
        if (stg[i]==0)
        {
            dfs(i);
        }
    }
    for (i=1;i<=n;i++)
    {
        if (stg[i]==1&&dr[i]==1)
        {
            g<<"0";
        }
        else
        if (stg[i]==0&&dr[i]==1)
        {
            g<<"1";
        }
        else
        if (stg[i]==0&&dr[i]==0)
        {
            g<<"3";
        }
        else
        {
            g<<"2";
        }
        g<<'\n';
    }
    return 0;
}