#include <fstream>
#include <vector>
const int NMAX=200005;

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

bool pair_up(int);
void dfs1(int, int);

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

int main()
{
    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);
    }
    for(i=2; i<=2*n+1; i++)
    {
        if(!gasit[i])
        {
            nrc++;
            dfs1(i, 0);
        }
    }
    for(i=1; i<=nrc; i++)
    {
        ans+=max(f[i][1], f[i][0]);
        if(f[i][1]>f[i][0])
        {
            for(auto i:partitie[i][1])
            {
                stare[i/2][i%2]=true;
            }
        }
        else
        {
            for(auto i:partitie[i][0])
            {
                stare[i/2][i%2]=true;
            }
        }
    }
    fout<<ans<<'\n';
    for(i=1; i<=n; i++)
    {
        if(stare[i][1]==stare[i][0])
        {
            if(stare[i][1]==true) fout<<3<<'\n';
            else fout<<0<<'\n';
        }
        else
        {
            if(stare[i][1]==true) fout<<2<<'\n';
            else fout<<1<<'\n';
        }
    }
    return 0;
}

void dfs1(int nod, int part)
{
    gasit[nod]=nrc;
    partitie[nrc][part].push_back(nod);
    f[nrc][part]++;
    for(auto i:v[nod])
    {
        if(!gasit[i])
            dfs1(i, 1-part);
    }
}


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(i))
        {
            cuplat[i]=nod;
            cuplat[nod]=i;
            return true;
        }
    }
    return false;
}