#include <bits/stdc++.h>
#define NMAX 8200

using namespace std;

ifstream f("felinare.in");
ofstream g("felinare.out");

int n, m, Left[NMAX], Right[NMAX], L[NMAX], R[NMAX];
bitset <NMAX> v;
vector <int> edges[NMAX];

bool cuplaj(int nod)
{
    if(v[nod])
       return 0;
    v[nod] = 1;

    for(auto k : edges[nod])
        if(!R[k])
        {
            Left[nod] = 1;
            L[nod] = k;
            R[k] = nod;
            return 1;
        }

    for(int k : edges[nod])
        if(cuplaj(R[k]))
        {
            Left[nod] = 1;
            L[nod] = k;
            R[k] = nod;
            return 1;
        }
    return 0;
}

void dfs(int nod)
{
    Left[nod] = 0;
    for(auto k : edges[nod])
        if(!Right[k])
        {
            Right[k] = 1;
            dfs(R[k]);
        }
}

int main()
{
    f >> n >> m;

    for(int i = 1; i <= n; i++)
    {
        int x, y;
        f >> x >> y;
        edges[x].push_back(y);
    }


    bool ok;
    do
    {
        ok = 0;
        v.reset();
        for(int i = 1; i <= n; i++)
            if(!L[i])
                ok |= cuplaj(i);
    }while(ok);

    int ans = 0;
    for(int i = 1; i <= n; i++)
        if(L[i])
            ans++;

    g << 2 * n - ans << "\n";

    v.reset();
    for(int i = 1; i <= n; i++)
        if(!Left[i])
            dfs(i);

    for(int i = 1; i <= n; i++)
    {
        Left[i] ^= 1;
        Right[i] ^= 1;
        g << Left[i] + 2 * Right[i] << "\n";
    }

    return 0;
}