#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];
int L[Nmax], R[Nmax];
int used[Nmax];
int SL[Nmax], SR[Nmax];
int inDeg[Nmax], outDeg[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)
{
    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);
        inDeg[y]++;
        outDeg[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;
    for(int i = 1; i <= N; i++)
        if(!SL[i])
            support(i);
    for(int i = 1; i <= N; i++)
    {
        int ans = (SL[i] + 2 * SR[i]);
        if(outDeg[i] == 0)
            ans |= 1;
        if(inDeg[i] == 0)
            ans |= 2;
        fout << ans << "\n";
    }
    return 0;
}