#include <fstream>
#include <vector>
#define NMAX 8200

using namespace std;

vector <int> v[NMAX], l, r, cl, cr, viz;
int step = 1, matched;

bool cuplaj(int nod)
{
    if(viz[nod] == step)
        return false;

    viz[nod] = step;


    for(int i = 0; i<v[nod].size(); ++i){
        int x = v[nod][i];
        if(!r[x] || cuplaj(r[x])){
            if(!r[x])
                ++matched;
            r[x]    = nod;
            l[nod]  = x;

            return true;
        }
    }

    return false;
}

void dfs(int nod)
{
    for(int i = 0; i<v[nod].size(); ++i){
        int x = v[nod][i];
        if(!cr[x]){
            cr[x]    = 1;
            cl[r[x]] = 0;

            dfs(r[x]);
        }
    }
}

int main()
{
    ifstream f("felinare.in");
    ofstream g("felinare.out");

    int n, m;
    f >> n >> m;

    l   = vector<int> (n + 1, 0);
    r   = vector<int> (n + 1, 0);
    cl  = vector<int> (n + 1, 0);
    cr  = vector<int> (n + 1, 0);
    viz = vector<int> (n + 1, 0);

    for(int i = 0; i < m; ++i){
        int x, y;
        f >> x >> y;
        v[x].push_back(y);
    }

    for(bool ok = true; ok; ++step){
        ok = false;
        for(int i = 1; i <= n; ++i)
            if(!l[i])
                ok |= cuplaj(i);
    }

    for(int i = 1; i <= n; ++i)
        if(l[i])
            cl[i] = 1;

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

    g << 2*n - matched << '\n';
    for(int i = 1; i <= n; ++i)
        g << 3 - cl[i] - cr[i]*2 << '\n';

    return 0;
}