#include <fstream>
#include <vector>
#include <bitset>
#define DIM 8300

using namespace std;

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

int nodeNum, edgeNum, matched;
int toLeft[DIM], toRight[DIM], support[DIM];

vector<int> graph[DIM];

bitset<DIM> visited;

bool verify = true;

bool makeMatch(int currentNode, int nextNode){
    toLeft[nextNode] = currentNode;
    toRight[currentNode] = nextNode;
    return true;
}

bool match(int currentNode){
    if(visited[currentNode])
        return false;
    visited[currentNode] = true;
    
    for(auto nextNode : graph[currentNode]){
        if(!toLeft[nextNode]){
            return makeMatch(currentNode, nextNode);
        }
    }
    
    for(auto nextNode : graph[currentNode]){
        if(match(toLeft[nextNode])){
            return makeMatch(currentNode, nextNode);
        }
    }
    
    return false;
}

void minSupport(int currentNode){
    for(auto nextNode : graph[currentNode]){
        if(!support[nextNode]){
            support[nextNode] = true;
            support[toLeft[nextNode]] = false;
            minSupport(toLeft[nextNode]);
        }
    }
}

int main(int argc, const char * argv[]) {
    in>>nodeNum>>edgeNum;
    for(int edgeCnt = 1; edgeCnt <= edgeNum; ++ edgeCnt){
        int node1, node2;
        in>>node1>>node2;
        graph[node1].push_back(node2 + nodeNum);
    }
    
    while(verify){
        verify = false;
        visited.reset();
        for(int nodeCnt = 1; nodeCnt <= nodeNum; ++ nodeCnt){
            if(!toRight[nodeCnt])
                verify |= match(nodeCnt);
        }
    }
    
    for(int nodeCnt = 1; nodeCnt <= nodeNum; ++ nodeCnt){
        if(toRight[nodeCnt]){
            ++ matched;
            support[nodeCnt] = 1;
        }
    }
    
    out<<2 * nodeNum - matched<<'\n';
    
    for(int nodeCnt = 1; nodeCnt <= nodeNum; ++ nodeCnt){
        if(!toRight[nodeCnt])
            minSupport(nodeCnt);
    }
    
    for(int nodeCnt = 1; nodeCnt <= nodeNum; ++ nodeCnt){
        if(support[nodeCnt] == support[nodeCnt + nodeNum]){
            if(support[nodeCnt])
                out<<"0\n";
            else
                out<<"3\n";
        }
        else{
            if(support[nodeCnt])
                out<<"2\n";
            else
                out<<"1\n";
        }
    }
    
    
    
    
    
    return 0;
}