#include <stdio.h>
#include <vector>
#include <bitset>

using namespace std;

#define maxN            10000
#define pb              push_back
#define forI(it, v)     for(vector <int> :: iterator it = (v).begin(); it != (v).end(); ++ it)

vector <int> G[maxN];
bitset <maxN> viz;
int l[maxN], r[maxN], S[2 * maxN], N, M;

int cupleaza (int nod) {
        if (viz[nod])   return 0;
        viz[nod] = 1;
        
        forI (it, G[nod])
                if (! r[*it]) {
                        l[nod] = *it;
                        r[*it] = nod;
                        return 1;
                }
                
        forI (it, G[nod])
                if (cupleaza (r[*it])) {
                        l[nod] = *it;
                        r[*it] = nod;
                        return 1;
                }
                
        return 0;
}

void solve (int nod) {
        forI(it, G[nod])
                if (! S[*it + N]) {
                        S[*it + N] = 1;
                        S[r[*it]] = 0;
                        solve (r[*it]);
                }
}

int main () {
        int a, b, sol, i;
        
        freopen("felinare.in", "r", stdin);
        freopen("felinare.out", "w", stdout);
        
        scanf("%d%d", &N, &M);
        
        for ( ; M -- ; ) {
                scanf("%d%d", &a, &b);
                G[a].pb (b);
        }

        for (i = 1, sol = 2 * N; i <= N; ++ i)
                if (! l[i]) {
                        viz.reset ();
                        sol -= cupleaza (i);
                }
              
        printf("%d\n", sol);
          
        for (i = 1; i <= N; ++ i)
                if (l[i])
                        S[i] = 1;
                        
        for (i = 1; i <= N; ++ i)
                if (! l[i]) {
                        solve (i);
                }
                
        for (i = 1; i <= N; ++ i) {
                int now = 3;
                if (S[i])       now --;
                if (S[i + N])   now -= 2;
                
                printf("%d\n", now);
        }
}