#include <fstream>
#include <vector>
#pragma GCC optimize("Ofast")
const int NMAX=200005;

using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");

bool pair_up(int);
void minimum_vertex_cover(int);

vector<int> v[NMAX], partitie[NMAX][3], muchii[NMAX], nodes;
int n, m, cplm, nrc, ans;
int cuplat[NMAX], gasit[NMAX], f[NMAX][3], stare[NMAX][3];
bool viz[NMAX], use[NMAX], mvc[NMAX];

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0); fout.tie(0);
    int i, a, b;
    bool ok=true;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>a>>b;
        v[2*a].push_back(2*b+1);
        v[2*b+1].push_back(2*a);
    }
    while(ok)
    {
        ok=false;
        for(i=2; i<=2*n+1; i+=2) viz[i]=false;
        for(i=2; i<=2*n+1; i+=2)
        {
            if(!cuplat[i] && pair_up(i))
            {
                nrc++;
                ok=true;
            }
        }
    }
    fout<<2*n-nrc<<'\n';
    for(i=2; i<=2*n+1; i+=2)
    {
        if(cuplat[i]) muchii[cuplat[i]].push_back(i);
        for(int j:v[i])
            if(j!=cuplat[i]) muchii[i].push_back(j);
    }
    for(i=2; i<=2*n+1; i+=2)
        if(!use[i]&&!cuplat[i]) minimum_vertex_cover(i);
    for(i=2; i<=2*n+1; i++)
    {
        if(use[i]&&i%2==1) mvc[i]=true;
        if(!use[i]&&i%2==0) mvc[i]=true;
    }
    for(i=1; i<=n; i++)
    {
        if(!mvc[2*i] && !mvc[2*i+1]) fout<<3<<'\n';
        else if(!mvc[2*i]) fout<<1<<'\n';
        else if(!mvc[2*i+1]) fout<<2<<'\n';
        else fout<<0<<'\n';
    }
    return 0;
}

void minimum_vertex_cover(int nod)
{
    use[nod]=1;
    for(int i:muchii[nod])
    {
        if(!use[i])
            minimum_vertex_cover(i);
    }
}


bool pair_up(int nod)
{
    if(viz[nod]) return false;
    viz[nod]=true;
    for(auto i:v[nod])
    {
        if(!cuplat[i])
        {
            cuplat[i]=nod;
            cuplat[nod]=i;
            return true;
        }
    }
    for(auto i:v[nod])
    {
        if(pair_up(cuplat[i]))
        {
            cuplat[i]=nod;
            cuplat[nod]=i;
            return true;
        }
    }
    return false;
}