#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

ifstream fin("felinare.in");
ofstream fout("felinare.out");

#define limn 8200

int N, M;
int L[limn], R[limn], cuplaj;
vector <int> G[limn];
bool viz[limn], minCover[2 * limn]; //min vertex cover in bipartite graph
// minCover[i] = 0 => felinar aprins
// minCover[i] = 1 => felinar stins

bool pairUp(int node) {
    if(viz[node])   
        return false;
    viz[node] = true;
    
    for(auto it:G[node]) 
        if(!R[it]) { 
            R[it] = node;
            L[node] = it;
            return true;
        }
    
    for(auto it:G[node])
        if(pairUp(R[it])) {
            R[it] = node;
            L[node] = it;
            return true;
        }
        
    return false;
}

void dfs(int node)
{
    for(auto it: G[node])
    {
        if(!minCover[it + N])
        {
            minCover[R[it]] = 0;
            minCover[it + N] = 1;
            dfs(R[it]);
        }
    }
}

int main()
{
    int x, y;
    
    fin>>N>>M;
    for(int i = 1; i <= M; i++)
    {
        fin >> x >> y;
        G[x].push_back(y);
    }
    
    // formeaza cuplajul maxim in graf bipartit
    bool pathFound = 1;
    while(pathFound)
    {
        pathFound = 0;
        memset(viz, 0, sizeof viz);
        for(int i = 1; i <= N; i++)
            if(!L[i])
                pathFound |= pairUp(i);
    }
    
    for(int i = 1; i <= N; i++)
        if(L[i])
        {
            cuplaj++;
            minCover[i] = 1;
        }
    fout << 2 * N - cuplaj << '\n'; // afisam nr de felinare ce pot fi aprinse

    for(int i = 1; i <= N; i++)
        if(!L[i])
            dfs(i);
            
    for(int i = 1; i <= N; i++)
    {
        if(minCover[i] && minCover[N + i])
            fout << "0\n";
        if(!minCover[i] && minCover[N + i])
            fout << "1\n";
        if(minCover[i] && !minCover[N + i])
            fout << "2\n";
        if(!minCover[i] && !minCover[N + i])
            fout << "3\n";
    }
    return 0;
}