#include <bits/stdc++.h>

using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
const int Nmax=2e4+5;
vector<int> v[Nmax];
int pl[Nmax],pr[Nmax];
bitset<2*Nmax> viz;
bool augment(int nod)
{
    for(int u:v[nod])
    {
        if(!viz[u])
        {
            viz[u]=1;
            if(!pr[u] || augment(pr[u]))
            {
                pr[u]=nod;
                pl[nod]=u;
                return 1;
            }
        }
    }
    return 0;
}
void mvc(int nod)
{
    for(int u:v[nod])
    {
        if(!viz[u])
        {
            viz[u]=1;
            viz[pr[u]]=0;
            mvc(pr[u]);
        }
    }
}
int main()
{
    int n,m;
    fin>>n>>m;
    int cnt=0;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        v[x].push_back(y+n);
        ///v[y+n].push_back(x);
    }
    bool ok=1;
    while(ok)
    {
        ok=0;
        viz.reset();
        for(int i=1;i<=n;i++)
        {
            if(pl[i]==0)
            {
                bool v=augment(i);
                if(v)
                {
                    ok=1;
                }
                cnt+=v;
            }
        }
    }
    viz.reset();
    for(int i=1;i<=n;i++)
    {
        if(pl[i]!=0) viz[i]=1;
    }
    for(int i=1;i<=n;i++)
    {
        if(pl[i]==0)
        {
            mvc(i);
        }
    }
    fout<<2*n-cnt<<'\n';
    for(int i=1;i<=n;i++)
    {
        if(pl[i]!=0 && pl[i+n]!=0)
        {
            fout<<0<<'\n';
        }
        else if(pl[i]!=0 && pl[i+n]==0)
        {
            fout<<2<<'\n';
        }
        else if(pl[i]==0 && pl[i+n]==0)
        {
            fout<<3<<'\n';
        }
        else fout<<1<<'\n';
    }
    return 0;
}