#include <bits/stdc++.h>
using namespace std;

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

const int N_MAX = 9000;

int L[N_MAX], R[N_MAX], L_grade[N_MAX], R_grade[N_MAX], N, M;

vector<pair<int, int>>  bulbs_state(N_MAX, {0, 0});

vector<vector<int>> graph(N_MAX, vector<int>());

vector<bool> visited(N_MAX, false);


bool pair_up(int left_node)
{
    if(visited[left_node] == true) return false;

    visited[left_node] = true;

    for(int right_node : graph[left_node])
    {
        if(L[right_node] == 0)
        {
            L[right_node] = left_node;
            R[left_node] = right_node;

            return true;
        }
    }

    for(int right_node : graph[left_node])
    {
        if(pair_up(L[right_node]) == true)
        {
            L[right_node] = left_node;
            R[left_node] = right_node;

            return true;
        }
    }

    return false;
}


int main()
{
    fin >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        int A, B;
        fin >> A >> B;

        graph[A].push_back(B);

        L_grade[A]++;
        R_grade[B]++;
    }

    bool no_changes = false;
    int coupling_cardinal = 0;

    while(no_changes == false)
    {
        fill(visited.begin(), visited.end(), false);
        no_changes = true;

        for(int i = 1; i <= N; ++i)
        {
            if(R[i] != 0) continue;
            if(pair_up(i) == false) continue;

            ++coupling_cardinal;
            no_changes = false;
        }
    }

    fout << 2 * N - coupling_cardinal << '\n';

    int first_used = 0, second_used = 0;

    for(int i = 1; i <= N; ++i)
    {
        if(L_grade[i] == 0)
        {
            bulbs_state[i].first = 1;
            first_used++;
        }


        if(R_grade[i] == 0)
        {
            bulbs_state[i].second = 1;
            second_used++;
        }
    }


    if(first_used < second_used)
    {
        for(int i = 1; i <= N; ++i)
        {
            bulbs_state[i].first = 1;
            if(L[i] == 0) bulbs_state[i].second = 1;
        }
    }
    else
    {
        for(int i = 1; i <= N; ++i)
        {
            bulbs_state[i].second = 1;
            if(R[i] == 0) bulbs_state[i].first = 1;
        }
    }

    for(int i = 1; i <= N; ++i)
    {
        if(bulbs_state[i].first == 0 && bulbs_state[i].second == 0) fout << "0\n";
        if(bulbs_state[i].first == 1 && bulbs_state[i].second == 0) fout << "1\n";
        if(bulbs_state[i].first == 0 && bulbs_state[i].second == 1) fout << "2\n";
        if(bulbs_state[i].first == 1 && bulbs_state[i].second == 1) fout << "3\n";
    }


}