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

#define Nmax 10100
#define Neighbour Graph[Node][i]

using namespace std;

vector <int> Graph[Nmax];
int N, M, Solution, Left[Nmax], Right[Nmax];
bool used[Nmax], supportLeft[Nmax], supportRight[Nmax];

void support(int Node) {

    for(int i = 0; i < Graph[Node].size(); i++)
        if(Left[Neighbour] == 0) {
            supportLeft[Neighbour] = true;
            supportRight[Left[Neighbour]] = false;
            support(Left[Neighbour]);
            }

}
bool hookUp(int Node) {

    int i;

    if(used[Node])
        return false;

    used[Node] = true;

    for(i = 0; i < Graph[Node].size(); i++)
        if(Left[Neighbour] == 0) {

            Left[Neighbour] = Node;
            Right[Node] = Neighbour;
            supportRight[Node] = true;

            return true;

            }

    for(i = 0; i < Graph[Node].size(); i++)
        if(hookUp(Left[Neighbour])) {

            Left[Neighbour] = Node;
            Right[Node] = Neighbour;
            supportRight[Node] = true;

            return true;

            }

    return false;

}
void Solve() {

    int i, last = -1;

    while(last < Solution) {

        last = Solution;
        memset(used, 0, sizeof(used));

        for(i = 1; i <= N; i++)
            if(Right[i] == 0)
                if(hookUp(i))
                    ++Solution;

        }

    for(i = 1; i <= N; i++)
        if(!supportRight[i])
            support(i);

}
void Read() {

    int x, y, M;
    ifstream in("felinare.in");

    in >> N >> M;

    while(M--) {

        in >> x >> y;
        Graph[x].push_back(y);

        }

    in.close();

}
void Write() {

    ofstream out("felinare.out");

    out << (2 * N - Solution) << '\n';
    for(int i = 1; i <= N; i++)
        out << (supportRight[i] ^ 1 | ((supportLeft[i] ^ 1) << 1)) << '\n';

    out.close();

}
int main() {

    Read();
    Solve();
    Write();

    return 0;
}