#include <fstream>
#include <vector>
#define dim 8191
using namespace std;
ifstream fin ("felinare.in");
ofstream fout ("felinare.out");
bool vis[dim+1];
int n,m,l[dim+1],r[dim+1],mvcl[dim+1],mvcr[dim+1];
vector <int> v[dim+1];
void read ()
{
    int x,y;
    fin>>n>>m;
    for (int i=1; i<=n; i++)
    {
        fin>>x>>y;
        v[x].push_back (y);
    }
}
bool cuplaj (int nod)
{
    if (vis[nod])
        return 0;
    vis[nod]=1;
    for (int i=0; i<(int)v[nod].size (); i++)
    {
        int vecin=v[nod][i];
        if (r[vecin]==0)
        {
            l[nod]=vecin;
            r[vecin]=nod;
            return 1;
        }
    }
    for (int i=0; i<(int)v[nod].size (); i++)
    {
        int vecin=v[nod][i];
        if (cuplaj (r[vecin]))
        {
            l[nod]=vecin;
            r[vecin]=nod;
            return 1;
        }
    }
    return 0;
}
void get_cuplaj ()
{
    long long sol=0;
    bool ok=1;
    while (ok)
    {
        ok=0;
        for (int i=1; i<=n; i++)
            vis[i]=0;
        for (int i=1; i<=n; i++)
        {
            if (l[i]==0&&cuplaj (i))
                ok=1;
        }
    }
    for (int i=1; i<=n; i++)
    {
        vis[i]=0;
        sol+=(l[i]!=0);
    }
    fout<<2*n-sol<<"\n";
}
void mvc (int nod)
{
    for (int i=0; i<(int)v[nod].size (); i++)
    {
        int vecin=v[nod][i];
        if (mvcr[vecin]==0)
        {
            mvcr[vecin]=1;
            mvcl[r[vecin]]=0;
            mvc (r[vecin]);
        }
    }
}
void get_mvc ()
{
    for (int i=1; i<=n; i++)
    {
        if (l[i])
            mvcl[i]=1;
    }
    for (int i=1; i<=n; i++)
    {
        if (!mvcl[i])
            mvc (i);
    }
    for (int i=1; i<=n; i++)
        fout<<(1-mvcl[i])*1+(1-mvcr[i])*2<<"\n";
}
int main ()
{
    read ();
    get_cuplaj ();
    get_mvc ();
    return 0;
}