using namespace std;

#include<iostream>
#include<fstream>
#include<vector>
#define pb push_back
#define nmax 10000
vector<int> G[nmax];
int l[nmax],r[nmax],viz[nmax],sl[10000],sr[10000];
int N,M;
ofstream fout("felinare.out");


bool dfs(int x)
{
    if(viz[x]==1) return 0;
    viz[x]=1;
    vector<int>::iterator it;

    for(it=G[x].begin();it<G[x].end();it++)
    if(!l[*it])
    {
        l[*it]=x;
        r[x]=*it;
        return 1;

    }
    for(it=G[x].begin();it<G[x].end();it++)
    if(dfs(l[*it]))
    {
        l[*it]=x;
        r[x]=*it;
        return 1;
    }

    return 0;

}


void suport_minim(int x)
{ vector<int>::iterator it;
   for(it=G[x].begin();it<G[x].end();it++)
   {
       if(!sr[*it])
       {
           sr[*it]=1;
           sl[l[*it]]=0;
           suport_minim(l[*it]);
       }
   }
}

void solve()
{
    int i,ok=1,flow=0;

    while(ok)
    {   ok=0;
        for(i=1;i<=N;i++) viz[i]=0;

        for(i=1;i<=N;i++)
          if(!r[i])
            if(dfs(i))
            {
                ok=1;
                flow++;
            }
    }

    fout<<N*2-flow<<"\n";
    for(i=1;i<=N;i++)
    {
        if(r[i])
          sl[i]=1;
    }
    for(i=1;i<=N;i++)
    {
        if(!r[i])
          suport_minim(i);
    }
    for(i=1;i<=N;i++)
    {
        if(sl[i] && sr[i]) fout<<0<<"\n";
        if(!sl[i] && sr[i]) fout<<1<<"\n";
        if(sl[i] && !sr[i]) fout<<2<<"\n";
        if(!sl[i] && !sr[i]) fout<<3<<"\n";
    }
}

void cit()
{int i,x,y;
    ifstream fin("felinare.in");
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y;
        G[x].pb(y);
    }

    fin.close();
}

int main()
{
    cit();

    solve();

    fout.close();

    return 0;
}