#include <bits/stdc++.h>

#define MaxN 8200

std::ifstream InFile("felinare.in");
std::ofstream OutFile("felinare.out");

int M;

template <int NNodes>
class DirectedGraph {
public:
    DirectedGraph() {
        for (int i=0; i<NNodes; ++i)
            Node[i].State = 3;
    }

    int N, NMatches;
    inline void AddEdge(int x, int y) {
        Node[x].ADC.push_back(y);
        Node[y].ADC.push_back(x);
    }

    bool PairUp(int Index) {
        if(Seen[Index]) return false;
        Seen[Index] = 1;

        for (std::list <int>::iterator Vecin = Node[Index].ADC.begin(); Vecin != Node[Index].ADC.end(); ++Vecin)
            if (!Node[*Vecin].Pair || PairUp(Node[*Vecin].Pair)) {
                Node[*Vecin].Pair = Index;
                Node[Index].Pair = *Vecin;
                return true;
            }   return false;
    }

    void Match() {
        bool bContinue;
        do {
            bContinue = 0;
            for (int i=0; i<2*N; ++i)
                Seen[i+1] = 0;
            for (int i=0; i<N; ++i)
                if(!Node[i+1].Pair)
                    bContinue |= PairUp(i+1);
        }   while(bContinue);

        for (int i=0; i<N; ++i)
            if (Node[i+1].Pair) NMatches++;
    }

    void Print() {
        OutFile << 2*N - NMatches << '\n';

        for (int i=0; i<N; ++i) // Greedy FTW
            if(Node[i+1].Pair) {
                if (Node[i].ADC.size() < Node[Node[i+1].Pair].ADC.size())
                    Node[i].State = 2;
                else if (Node[i].ADC.size() < Node[Node[i+1].Pair].ADC.size())
                    Node[i].State = 1;
                else
                    Node[i].State = 0;
            }

        for (int i=0; i<N; ++i)
            OutFile << (int)Node[i].State << '\n';
    }

private:
    bool Seen[NNodes];

    struct GraphNode {
        std::list <int> ADC;
        char State;
        int Pair;
    }   Node[NNodes];

};  DirectedGraph <2*MaxN> Graph;

void Citire() {
    InFile >> Graph.N >> M;
    for (int i=0, x, y; i<M; ++i)
        InFile >> x >> y,
        Graph.AddEdge(x, y+Graph.N);
}

void Rezolvare() {
    Graph.Match();
    Graph.Print();
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}