//#include <iostream>
#include <fstream>
using namespace std;

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

#define LE 8666
#define pb push_back
#include <vector>
#define x first
#define y second
#define mp make_pair
#define cout g

int l[LE],r[LE];
vector<int> H[LE],M[LE+LE];
bool viz[LE],viz2[LE+LE],BAD[LE+LE];
pair<int,int> E[LE*3];
bool cm[LE+LE];

bool pair_up(int nod)
{
    viz[nod]=true;
    int N=H[nod].size(),i;

    for(i=0; i<N; ++i)
    {
        int D=H[nod][i];

        if (r[D]==0)
        {
            l[nod]=D;
            r[D]=nod;
            return true;
        }

        if (viz[r[D]]==false)
            if (pair_up(r[D]))
            {
                l[nod]=D;
                r[D]=nod;
                return true;
            }
    }
    return false;
}

void dfs(int nod)
{
    viz2[nod]=true;
    int N=M[nod].size(),i;

    for(i=0; i<N; ++i)
    {
        int D=M[nod][i];
        if (viz2[D]) continue;
        dfs(D);
    }
}
int main()
{
    int n,m,i;
    f>>n>>m;

    for(i=1; i<=m; ++i)
    {
        f>>E[i].x>>E[i].y;
        H[E[i].x].pb(E[i].y);

        cm[E[i].x]=cm[E[i].x+n]=cm[E[i].y]=cm[E[i].y+n]=true;
    }


    while (true)
    {
        for(i=1; i<=n; ++i) viz[i]=false;

        bool okz=false;

        for(i=1; i<=n; ++i)
            if (viz[i]==false)
                if (l[i]==0)
                    okz|=pair_up(i);

        if (okz==false) break;
    }

    for(i=1; i<=m; ++i)
        if (l[E[i].x]==E[i].y)
            M[E[i].y+n].pb(E[i].x);
        else
            M[E[i].x].pb(E[i].y+n);

    for(i=1; i<=n; ++i)
        if (l[i]==0)
            M[0].pb(i);
        else
            M[i].pb(0);

    for(i=n+1; i<=n+n; ++i)
        if (r[i]==0)
            M[i].pb(n+n+1);
        else
            M[n+n+1].pb(i);

    dfs(0);

    for(i=1; i<=n; ++i)
        if (viz2[i]==false)
            BAD[i]=true;

    for(i=n+1; i<=n+n; ++i)
        if (viz2[i]==true)
            BAD[i]=true;

    for(i=1; i<=m; ++i)
        if (viz2[E[i].x]^viz2[E[i].y+n])
            BAD[i]=true;

    int nr_res=n+n;

    for(i=1; i<=n; ++i)
        if (cm[i]==false&&cm[i+n]==false)
            BAD[i]=BAD[i+n]=false;

    for(i=1; i<=n; ++i)
        if (l[i])
            --nr_res;

    cout<<nr_res<<'\n';

  //  for(i=1; i<=n; ++i) BAD[i]^=true;

    for(i=1; i<=n; ++i)
    {
        if (BAD[i]==false&&BAD[i+n]==false)
        {
            cout<<3<<'\n';
            continue;
        }

        if (BAD[i]==true&&BAD[i+n]==false)
        {
            cout<<2<<'\n';
            continue;

        }

        if (BAD[i]==true&&BAD[i+n]==true)
            cout<<0<<'\n';
        else
            cout<<1<<'\n';
    }





    return 0;
}