#include<fstream>
#include<vector>
#include<cstring>
#define DIM 8192
using namespace std;
ifstream cin("felinare.in");
ofstream cout("felinare.out");
vector<int>G[DIM];
bool rs[DIM],ls[DIM],v[DIM];
int r[DIM],l[DIM],N,M,i;
bool cuplaj(int nod)
{
    if(v[nod])
        return 0;
    v[nod]=1;
    for(unsigned i=0;i<G[nod].size();i++)
        if(!r[G[nod][i]])
        {
            l[nod]=G[nod][i];
            r[G[nod][i]]=nod;
            return 1;
        }
    for(unsigned i=0;i<G[nod].size();i++)
    {
        int value=r[G[nod][i]];
        if(!v[value] and cuplaj(value))
        {
            l[nod]=G[nod][i];
            r[G[nod][i]]=nod;
            return 1;
        }
    }
    return 0;
}
void suport(int nod)
{
    for(unsigned i;i<G[nod].size();i++)
    {
        int value=G[nod][i];
        if(rs[value])
            continue;
        rs[value]=1;
        ls[r[value]]=0;
        suport(r[value]);
    }
}
int main()
{
    cin>>N>>M;
    for(i=1;i<=M;i++)
    {
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
    }
    bool ok=1;
    int nr=0;
    while(ok)
    {
        ok=0;
        memset(v,0,sizeof(v));
        for(i=1;i<=N;i++)
            if(!l[i] and cuplaj(i))
            {
                nr++;
                ok=1;
            }
    }
    cout<<2*N-nr<<"\n";
    for(i=1;i<=N;i++)
        if(l[i])
            ls[i]=1;
    for(i=1;i<=N;i++)
        if(!ls[i])
            suport(i);
    for(i=1;i<=N;i++)
        if(ls[i] and rs[i])
            cout<<"0\n";
        else if(!ls[i] and rs[i])
            cout<<"1\n";
        else if(ls[i] and !rs[i])
            cout<<"2\n";
        else
            cout<<"3\n";
}