#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
vector<int> G[8200];
vector<int> Gt[8200];
bool viz[8200];
int left[8200];
int right[8200];
bool mark_left[8200];
bool mark_right[8200];
int pair_up(int u)
{
    if(viz[u]) return 0;
    viz[u]=true;
    for(vector<int>::iterator it=G[u].begin();it!=G[u].end();it++)
        if(!right[*it])
        {
            right[*it]=u;
            left[u]=*it;
            return 1;
        }
    for(vector<int>::iterator it=G[u].begin();it!=G[u].end();it++)
        if(right[*it] && pair_up(right[*it]))
        {
            right[*it]=u;
            left[u]=*it;
            return 1;
        }
    return 0;
}
int main()
{
    freopen("felinare.in","r",stdin);
    freopen("felinare.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int x,y,i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
    bool flag=true;int cuplaj=0;
    while(flag)
    {
        memset(viz,0,sizeof(viz));
        flag=false;
        for(int i=1;i<=n;i++)
            if(!left[i] && pair_up(i))
            {
                flag=true;
                cuplaj++;
            }
    }
    printf("%d\n",2*n-cuplaj);
    for(int i=1;i<=n;i++)
        if(left[i])
            mark_left[i]=true;
    for(int i=1;i<=n;i++)
        if(mark_left[i])
        {
            int nod=left[i];flag=true;
            for(vector<int>::iterator it=Gt[nod].begin();it!=Gt[nod].end();it++)
                if(!mark_left[*it])
                {
                    flag=false;
                    break;
                }
            if(!flag)
            {
                mark_left[i]=false;
                mark_right[left[i]]=true;
            }
        }
    for(int i=1;i<=n;i++)
        if(!mark_left[i] && !mark_right[i])
            printf("3\n");
        else if(mark_left[i] && !mark_right[i])
                printf("2\n");
            else if(!mark_left[i] && mark_right[i])
                    printf("1\n");
                else
                    printf("0\n");
    return 0;
}