#include<bits/stdc++.h>
using namespace std;
ifstream in("cuplaj.in");
ofstream out("cuplaj.out");
vector<int> v[8200];
int l[8200],r[8200];
bitset<8200> v1,v2;
bool f(int nr)
{
    if(v1[nr]) return 0;
    v1[nr]=1;
    for(auto it:v[nr])
        if(!r[it])
        {
            r[it]=nr;
            l[nr]=it;
            return 1;
        }
    for(auto it:v[nr])
        if(f(r[it]))
        {
            r[it]=nr;
            l[nr]=it;
            return 1;
        }
    return 0;
}
void dr(int nr)
{
    if(v1[nr]) return;
    v1[nr]=1;
    for(auto it:v[nr])
        if(l[nr]!=it&&!v2[it])
        {
            v2[it]=1;
            dr(r[it]);
        }
}
int main()
{
    int n,m,i,nr1,nr2;
    in>>n>>m;
    while(m--)
    {
        in>>nr1>>nr2;
        v[nr1].push_back(nr2);
    }
    while(nr1)
    {
        nr1=0;
        v1.reset();
        for(i=1;i<=n;i++)
            if(!l[i])
                nr1|=f(i);
    }
    v1.reset();
    for(i=1;i<=n;i++)
        if(!l[i])
            dr(i);
        else
            nr1++;
    out<<n*2-nr1<<"\n";
    for(i=1;i<=n;i++)
        out<<v1[i]+(!v2[i])*2<<"\n";
    return 0;
}