#include <bits/stdc++.h>

using namespace std;

ifstream in("felinare.in");
ofstream out("felinare.out");

vector <int> v[8200];
int n,m,ok = 1,st[10001],dr[10001],used[10001],contor,verif[20002];

int solve(int a)
{
    if(used[a])
        return 0;
    used[a] = 1;
    for(int i = 0;i < v[a].size();i++)
    {
        int x = v[a][i];
        if(dr[x] == 0)
        {
            dr[x] = a;
            st[a] = x;
            return 1;
        }
    }
    for(int i = 0;i < v[a].size();i++)
    {
        int x = v[a][i];
        if(solve(dr[x]))
        {
            dr[x] = a;
            st[a] = x;
            return 1;
        }
    }

    return 0;
}

void watafac(int a)
{
    for(int i = 0;i < v[a].size();i++)
    {
        int x = v[a][i];
        if(verif[x] == 0)
        {
            verif[x+n] = 1;
            verif[dr[x]] = 0;
            watafac(dr[x]);
        }
    }
}

int main()
{
    in>>n>>m;
    for(int i = 1;i<=m;i++)
    {
        int x,y;
        in>>x>>y;
        v[x].push_back(y);
    }

    while(ok)
    {
        ok = 0;
        for(int i = 1;i<=n;i++)
            used[i] = 0;
        for(int i = 1;i<=n;i++)
            if(st[i] == 0)
                ok += solve(i);
    }

    for(int i = 1;i<=n;i++)
    {
        if(st[i])
            contor++,   verif[i] = 1;
    }
    out<<2*n-contor<<"\n";
    for(int i = 1;i<=n;i++)
    {
        if(st[i] == 0)
            watafac(i);
    }
    for(int i = 1;i<=n;i++)
    {
        int k = 3;
        if(verif[i])
            k--;
        if(verif[i+n])
            k -= 2;
        out<<k<<"\n";
    }


    return 0;
}