#include <bits/stdc++.h>

using namespace std;
ifstream in("felinare.in");
ofstream out("felinare.out");
const int N = 1<<13;
vector<int> v[N];
int L[N],R[N];
bool viz[N],useL[N],useR[N];
bool Match(int x)
{
    if (viz[x])
        return 0;
    viz[x] = 1;
    for (auto it: v[x])
        if (!L[it])
        {
            L[it] = x;
            R[x] = it;
            return 1;
        }
    for (auto it: v[x])
        if (Match(L[it]))
        {
            L[it] = x;
            R[x] = it;
            return 1;
        }
    return 0;
}
void dfs(int x)
{
    for (auto it: v[x])
        if (!useR[it])
        {
            useR[it] = 1;
            useL[L[it]] = 0;
            dfs(L[it]);
        }
}
int main()
{
    int n,m;
    in >> n >> m;
    for (int i = 1; i<=m; i++)
    {
        int x,y;
        in >> x >> y;
        v[x].push_back(y);
    }
    bool ok = 1;
    while (ok)
    {
        ok = 0;
        memset(viz,0,sizeof(viz));
        for (int i = 1; i<=n; i++)
            if (!R[i])
                ok|=Match(i);
    }
    for (int i = 1; i<=n; i++)
        if (R[i])
            useL[i] = 1;
    int ans = 2*n;
    for (int i = 1; i<=n; i++)
    {
        if (!R[i])
            dfs(i);
        if (L[i])
            ans--;
    }
    out << ans << "\n";
    for (int i = 1; i<=n; i++)
    {
        if (useL[i] && useR[i])
            out << "0\n";
        else if (useR[i])
            out << "1\n";
        else if (useL[i])
            out << "2\n";
        else
            out << "3\n";
    }
}