#include <bits/stdc++.h>

#define Nmax 8195

using namespace std;

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

int N, M;
vector <int> G[Nmax], Gt[Nmax];
int L[Nmax], R[Nmax];
int used[Nmax];
int SL[Nmax], SR[Nmax];
int ans[Nmax];

bool pairUp(int node)
{
    if(used[node])
        return false;
    used[node] = true;
    for(auto it : G[node])
        if(L[it] == 0)
        {
            L[it] = node;
            R[node] = it;
            return true;
        }
    for(auto it : G[node])
        if(pairUp(L[it]))
        {
            R[node] = it;
            L[it] = node;
            return true;
        }
    return false;
}

void support(int node)
{
    if(used[node])return;
    used[node] = true;
    for(auto it : G[node])
        if(!SR[it])
        {
            SR[it] = 1;
            SL[L[it]] = 0;
            support(L[it]);
        }
}

int main()
{
    fin >> N >> M;
    while(M--)
    {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
    for(bool ok = true; ok;)
    {
        ok = false;
        memset(used, false, sizeof(used));
        for(int i = 1; i <= N; i++)
            if(R[i] == 0)
                if(pairUp(i))
                    ok = true;
    }
    int cnt = 0;
    for(int i = 1; i <= N; i++)
        if(R[i] != 0)
            cnt++;
    fout << 2 * N - cnt << "\n";
    for(int i = 1; i <= N; i++)
        if(R[i] != 0)
            SL[i] = 1;
    memset(used, false, sizeof(used));
    for(int i = 1; i <= N; i++)
        if(!SL[i])
            support(i);
    for(int i = 1; i <= N; i++)
        ans[i] = 3;
    for(int i = 1; i <= N; i++)
    {
        if(SL[i])
            for(auto it : G[i])
                if(ans[it] & 2)
                    ans[it] -= 2;
        if(SR[i])
            for(auto it : Gt[i])
                if(ans[it] & 1)
                    ans[it] -= 1;
    }
    for(int i = 1; i <= N; i++)
        fout << ans[i] << "\n";
    return 0;
}