#include <bits/stdc++.h>

using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
const int Nmax=8200;
int st[Nmax],dr[Nmax],L[Nmax],R[Nmax],supL[Nmax],supR[Nmax];
vector<int>G[Nmax];
bitset<Nmax>viz;
bool pairup(int n)
{
    if(viz[n]) return 0;
    viz[n]=1;
    for(vector<int>::iterator it=G[n].begin();it!=G[n].end();it++)
    {
        if(R[*it]==0)
        {
            R[*it]=n;
            L[n]=*it;
            supL[n]=1;
            return 1;
        }
        if(pairup(R[*it]))
        {
            R[*it]=n;
            L[n]=*it;
            supL[n]=1;
            return 1;
        }
    }
    return 0;
}
void support(int n)
{
    for(vector<int>::iterator it=G[n].begin();it!=G[n].end();it++)
    {
        if(supR[*it]==0)
        {
            supR[*it]=1;
            supL[R[*it]]=0;
            support(R[*it]);
        }
    }
}
int main()
{
    int n,m,x,y,i,A=0,B=0,cuplaj=0;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        A++,B++;
        fin>>x>>y;
        G[x].push_back(y);
    }
    bool change=1;
    while(change)
    {
        change=0;
        viz.reset();
        for(i=1;i<=n;i++)
        {
            if(L[i]==0) change|=pairup(i);
        }
    }
    for(i=1;i<=n;i++)
    {
        if(L[i]>0) cuplaj++;
    }
    fout<<2*n-cuplaj<<"\n";
    for(i=1;i<=n;i++)
    {
        if(supL[i]==0) support(i);
    }
    for(i=1;i<=n;i++) fout<<1-supL[i]+2*(1-supR[i])<<"\n";
}