#include <fstream>
#include <cstring>
#include <vector>
#define N 9000
using namespace std;

vector<int>G[N];
int i, x, y, n, m, c, sr[N], sl[N], L[N], R[N];
bool ok, viz[N];

void suport(int x)
{
    vector<int> :: iterator it;
    for(it = G[x].begin(); it != G[x].end(); ++it)
    if(!sr[*it])
    {
        sr[*it] = 1;
        sl[R[*it]] = 0;
        suport(R[*it]);
    }
}

bool pairup(int x)
{
    vector<int> :: iterator it;

    if(viz[x]) return 0;
    for(it = G[x].begin(); it != G[x].end(); ++it)
    if(!R[*it])
    {
        R[*it] = x;
        L[x] = *it;
        c++;
        return 1;
    }
    for(it = G[x].begin(); it != G[x].end(); ++it)
    if(pairup(R[*it]))
    {
        R[*it] = x;
        L[x] = *it;
        return 1;
    }
    return 0;
}

int main()
{
    ifstream fi("felinare.in");
    ofstream fo("felinare.out");
    fi >> n >> m;
    for(i = 1; i <= m; i++)
    {
        fi >> x >> y;
        G[x].push_back(y);
    }
    for(ok = 1; ok; )
    {
        memset(viz, 0, sizeof(viz));
        ok = 0;
        for(i = 1; i <= n; i++)
            if(L[i] == 0 and pairup(i)) ok = 1;
    }
    for(i = 1; i <= n; i++) if(L[i]) sl[i] = 1;
    for(i = 1; i <= n; i++) if(!L[i]) suport(i);
    fo << 2*n - c << "\n";
    for(i = 1; i <= n; i++)
    {
        if(sl[i] and sr[i]) fo << "0\n";
        if(sl[i] and !sr[i]) fo << "2\n";
        if(sl[i] == 0 and sr[i]) fo << "1\n";
        if(sl[i] == 0 and !sr[i]) fo << "3\n";
    }
    return 0;
}