#include <bits/stdc++.h>

using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
int n,m,ok,viz[10000],st[10000],dr[10000],nr;
bool st2[10000],dr2[10000];
vector<int> v[10000];

int pairup(int i)
{
    if(viz[i]) return 0;
    viz[i]=1;
    for(int j=0; j<v[i].size(); j++)
    {
        int vec=v[i][j];
        if(!dr[vec] || pairup(dr[vec]))
        {
            st[i]=vec;
            dr[vec]=i;
            st2[i]=1;
            return 1;
        }
    }
    return 0;
}

void dfs(int i)
{
    for(int j=0;j<v[i].size();j++)
    {
        int vec=v[i][j];
        if(!dr[vec])
        {
            dr2[vec]=1;
            st2[dr[vec]]=0;
            dfs(dr[vec]);
        }
    }
}

int main()
{
    int x,y;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
    }
    ok=1;
    while(ok)
    {
        memset(viz,0,sizeof(viz));
        ok=0;
        for(int i=1;i<=n;i++)
        {
            if(dr[i]==0&&pairup(i))ok=1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(st[i])nr++;
    }
    fout<<2*n-nr<<'\n';
    for(int i=1;i<=n;i++)
        if(st2[i]==0)dfs(i);
    for(int i=1;i<=n;i++)
    {
        if(st2[i]==0&&dr2[i]==0)fout<<3;
        else if(st2[i]==1&&dr2[i]==0)fout<<2;
        else if(st2[i]==0&&dr2[i]==1)fout<<1;
        else fout<<0;
        fout<<'\n';
    }
}