#include <bits/stdc++.h>

using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
vector<int>nod[8200];
bool ap[8200];
int last[8200];
int c[8200];
int rez[8200];
int n,m,x,y;
bool go_visit(int pos,int t)
{
    if(last[pos]==t)return false;
    last[pos]=t;
    for(int i=0;i<nod[pos].size();i++)
        if(c[nod[pos][i]]==0 || go_visit(c[nod[pos][i]],t))
        {
            ap[pos]=true;
            c[nod[pos][i]]=pos;
            return true;
        }
    return false;
}
void mark(int pos)
{
    if(rez[pos]&1)return;
    rez[pos]+=1;
    for(int i=0;i<nod[pos].size();i++)
    {
        rez[nod[pos][i]]&=1;
        mark(c[nod[pos][i]]);
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        nod[x].push_back(y);
    }
    int counter=2*n;
    for(int i=1;i<=n;i++)
        counter-=go_visit(i,i);
    fout<<counter<<"\n";
    for(int i=1;i<=n;i++)rez[i]=2;
    for(int i=1;i<=n;i++)
        if(!ap[i])
            mark(i);
    for(int i=1;i<=n;i++)
        fout<<rez[i]<<"\n";
    return 0;
}