#include <cstdio>
#include <vector>

using namespace std;

const int NMAX = 8191;

int n, m, i, ans;
int dr[NMAX+5], st[NMAX+5];
bool used[NMAX+5], used2[NMAX+5];
vector <int> G[NMAX+5];

bool cupleaza(int node)
{
    int s=G[node].size(), i, son;

    if(used[node])
        return 0;

    used[node]=1;

    for(i=0; i<s; ++i)
    {
        son=G[node][i];

        if(!st[son] || cupleaza(st[son]))
        {
            st[son]=node;
            dr[node]=son;
            return 1;
        }
    }
    return 0;
}

void cuplaj()
{
    while(true)
    {
        bool ok=0;

        for(i=1; i<=n; ++i)
            used[i]=0;

        for(i=1; i<=n; ++i)
            if(!dr[i] && !used[i] && cupleaza(i))
                ok=1,++ans;

        if(!ok)
            return;
    }
}

void dfs(int node)
{
    int i, s=G[node].size(), son;

    for(i=0; i<s; ++i)
    {
        son=G[node][i];
        if(!used2[son])
        {
            used2[son]=1;
            used[st[son]]=0;
            dfs(st[son]);
        }
    }
}

void suport()
{
    int i;

    for(i=1; i<=n; ++i)
    {
        if(dr[i])
            used[i]=1;
        else used[i]=0;
        used2[i]=0;
    }

    for(i=1; i<=n; ++i)
        if(!dr[i])
            dfs(i);

    for(i=1; i<=n; ++i)
    {
        if(!used[i] && !used2[i])
            printf("3\n");
        if(used[i] && !used2[i])
            printf("2\n");
        if(!used[i] && used2[i])
            printf("1\n");
        if(used[i] && used2[i])
            printf("0\n");
    }
}

int main()
{
    freopen("felinare.in","r",stdin);
    freopen("felinare.out","w",stdout);

    scanf("%d%d", &n, &m);

    while(m--)
    {
        int a,b;
        scanf("%d%d", &a, &b);

        G[a].push_back(b);
    }

    cuplaj();

    printf("%d\n",2*n-ans);

    suport();

    return 0;
}