#include <bits/stdc++.h>
#define dim 8195
#define mmax 20005
using namespace std;
ifstream f("felinare.in");
ofstream g("felinare.out");
int n,m,ans;
vector <int> graph[dim];
bool checked[dim],left_felinar[dim],right_felinar[dim];
int Left[dim],Right[dim];
void Read()
{
    f>>n>>m;
    for(int i=1; i<=n; ++i)
    {
        int x,y;
        f>>x>>y;
        graph[x].push_back(y);
    }
}
bool Match(int node)
{
    if(checked[node])
        return false;
    checked[node]=true;
    for(int i=0; i<graph[node].size(); ++i)
    {
        int son=graph[node][i];
        if(!Right[son])
        {
            ++ans;
            left_felinar[node]=true;
            Right[son]=node;
            Left[node]=son;
            return true;
        }
    }
    for(int i=0; i<graph[node].size(); ++i)
    {
        int son=graph[node][i];
        if(Match(Right[son]))
        {
            left_felinar[node]=true;
            Right[son]=node;
            Left[node]=son;
            return true;
        }
    }
    return false;
}
void Cuplaj()
{
    bool okay;
    do
    {
        for(int i=1; i<=n; ++i)
            checked[i]=false;
        okay=false;
        for(int i=1; i<=n; ++i)
            if(!Left[i])
                okay|=Match(i);
    }
    while(okay);
}
void Felinar(int node)
{
    for(int i=0; i<graph[node].size(); ++i)
    {
        int son=graph[node][i];
        if(!right_felinar[son])
        {
            right_felinar[son]=true;
            left_felinar[Right[son]]=false;
            Felinar(Right[son]);
        }
    }
}
void Write()
{
    g<<2*n-ans<<'\n';
    for(int i=1; i<=n; ++i)
        if(!left_felinar[i])
            Felinar(i);
    for(int i=1; i<=n; ++i)
    {
        int ans=3;
        if(right_felinar[i])
            ans-=2;
        if(left_felinar[i])
            ans--;
        g<<ans<<"\n";
    }
}
int main()
{
    Read();
    Cuplaj();
    Write();
    return 0;
}