#include <bits/stdc++.h>

using namespace std;

ifstream fi( "felinare.in" );
ofstream fo( "felinare.out");

const int maxn = 8191;

vector < int > G[maxn + 1];

int n, m, Left[maxn], Right[maxn], l[maxn], r[maxn];
bool seen[maxn];

bool match( int node ) {
    if (seen[ node ])
        return 0;

    seen[ node ] = 1;
    for (int son: G[ node ]) {
        if (!Right[ son ]) {
            Left[ node ] = son;
            Right[ son ] = node;
            return 1;
        }
    }

    for (int son: G[ node ]) {
        if (match( son )) {
            Left[ node ] = son;
            Right[ son ] = node;
            return 1;
        }
    }

    return 0;
}

void dfs( int node ) {
    for (int son: G[ node ]) {
        if (r[ son ] == 0) {
            r[ son ] = 1;
            l[ Right[ son ] ] = 0;
            dfs( Right[ son ] );
        }
    }
}

int main()
{
    int x, y;

    fi >> n >> m;

    for (int i = 1; i <= m; i++) {
        fi >> x >> y;
        G[ x ].push_back( y );
    }

    int ok = 1, ans = 0;
    while (ok) {
        ok = 0;
        memset( seen, 0, sizeof seen );
        for (int node = 1; node <= n; node++)
            if (!Left[ node ])
                ok = ok | match( node );
    }

    for (int i = 1; i <= n; i++)
        if (Left[ i ])
            l[ i ] = 1, ans++;


    fo << 2 * n - ans << '\n';

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

    for (int i = 1; i <= n; i++)
        fo << (!l[ i ]) + (!r[ i ]) * 2 << '\n';

    fo.close();
    fi.close();

    return 0;
}