#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() {}

    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 DFSSuport(int Index) {
        for (std::list <int>::iterator Vecin = Node[Index].ADC.begin(); Vecin != Node[Index].ADC.end(); ++Vecin)
            if (!bSuport[*Vecin]) {      // Am gasit o muchie ce nu e acoperita: nu e bine
                bSuport[*Vecin] = 1;
                bSuport[Node[*Vecin].Pair] = 0;
                DFSSuport(Node[*Vecin].Pair);
            }
    }

    void FindStates() {
        for (int i=0; i<N; ++i)
            if (Node[i+1].Pair)
                bSuport[i+1] = 1;

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

    void Print() {
        OutFile << 2*N - NMatches << '\n';
        for (int i=0; i<N; ++i)
            OutFile << 2*(!bSuport[i+1+N]) + (!bSuport[i+1]) << '\n' ;
    }

private:
    bool bSuport[NNodes];
    bool Seen[NNodes];

    struct GraphNode {
        int Pair;
        std::list <int> ADC;
    }   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.FindStates();
    Graph.Print();
}

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

    return 0;
}