#include <bits/stdc++.h>

using namespace std;

#define MAX_N 8191

int n, m, cnt;
bitset <MAX_N + 5>  viz, mvcLeft, mvcRight;
vector <int> st, dr;
vector <vector <int> > graph;

bool pairUp(int node)
{
    if(viz[node] == 1)
        return 0;

    viz[node] = 1;

    for(int x : graph[node])
        if(!st[x])
        {
            cnt ++;
            st[x] = node;
            dr[node] = x;
            return 1;
        }

    for(int x : graph[node])
    {
        if(dr[node] != x  &&  pairUp(st[x]) == 1)// nu am nevoie neap de dr[node] != x ca daca dau
        {
            //pairUp din el e deja vizitat nodul si da return 0
            st[x] = node;
            dr[node] = x;
            return 1;
        }
    }
    return 0;
}

void check(int node)
{
    for(int x : graph[node])
        if(!mvcRight[x])
        {
            mvcLeft[node] = 0;
            mvcRight[x] = 1;
            check(st[x]);
        }
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    freopen("felinare.in", "r", stdin);
    freopen("felinare.out", "w", stdout);

    cin >> n >> m;
    graph.resize(n + 1);
    dr.resize(n + 1);
    st.resize(n + 1);

    for(int i = 1; i <= n; i ++)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
    }


    bool ok = 1;
    while(ok)
    {
        for(int i = 1; i <= n; i ++)
            viz[i] = 0;
        int copyCnt = cnt;
        for(int i = 1; i <= n; i ++)
            if(!dr[i])
                pairUp(i);
        if(cnt == copyCnt)
            ok = 0;
    }

    for(int i = 1; i <= n; i ++)
        if(dr[i])
            mvcLeft[i] = 1;

    for(int i = 1; i <= n; i ++)
        if(!dr[i])
            check(i);

    cout << 2 * n - cnt << "\n";
    for(int i = 1; i <= n; i ++)
    {
        if(!mvcLeft[i]  &&  !mvcRight[i])
            cout << "3\n";
        if(mvcLeft[i]  &&  !mvcRight[i])
            cout << "1\n";
        if(!mvcLeft[i]  &&  mvcRight[i])
            cout << "2\n";
        if(mvcLeft[i]  &&  mvcRight[i])
            cout << "0\n";
    }
    return 0;
}