#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
vector<int> G[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;
}
void solve(int i)
{
    for(vector<int>::iterator it=G[i].begin();it!=G[i].end();it++)
        if(!mark_right[*it])
        {
            mark_right[*it]=1;
            mark_left[left[*it]]=0;
            solve(right[*it]);
        }
}
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);
    }
    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])
            solve(i);
    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;
}