#include <fstream>
#include <bitset>
#include <vector>

#define NMAX 8205
using namespace std;

vector<int> graf[NMAX];
vector<int> graf_inv[NMAX];
bitset<NMAX> viz;
int st[NMAX];
int dr[NMAX];
bitset<NMAX> st_marc;
bitset<NMAX> dr_marc;

bool cupl(int nod)
{
    if(viz[nod])
        return 0;
    viz[nod]=1;

    for(vector<int>::iterator it=graf[nod].begin();it!=graf[nod].end();it++)
        if(!dr[*it]){
            st[nod]=*it;
            dr[*it]=nod;
            return 1;
        }

    for(vector<int>::iterator it=graf[nod].begin();it!=graf[nod].end();it++)
        if(cupl(dr[*it])){
            st[nod]=*it;
            dr[*it]=nod;
            return 1;
        }

    return 0;
}

void suport(int nod)
{
    for(vector<int>::iterator it=graf[nod].begin();it!=graf[nod].end();it++)
        if(!dr_marc[*it]){
            dr_marc[*it]=1;
            st_marc[dr[*it]]=0;
            suport(dr[*it]);
        }
}

int main()
{
    ifstream cin("felinare.in");
    ofstream cout("felinare.out");

    int n=0,m=0,a,b;
    cin>>n>>m;

    while(m--){
        cin>>a>>b;
        graf[a].push_back(b);
        graf_inv[b].push_back(a);
    }

    bool ok=true;
    while(ok){
        ok=false;
        viz&=0;

        for(int i=1;i<=n;i++)
            if(!st[i] && cupl(i))
                ok=true;
    }

    int cuplaj=0;
    for(int i=1;i<=n;i++)
        if(st[i]){
            cuplaj++;
            st_marc[i]=1;
        }

    for(int i=1;i<=n;i++)
        if(!st_marc[i])
            suport(i);

    cout<<2*n-cuplaj<<'\n';
    for(int i=1;i<=n;i++){
        st_marc[i]=1-st_marc[i];
        dr_marc[i]=1-dr_marc[i];

        cout<<((dr_marc[i]<<1)+st_marc[i])<<'\n';
    }

    /*ok=true;
    for(int i=1;i<=n;i++)
        for(vector<int>::iterator it=graf[i].begin();it!=graf[i].end();it++)
            if(!st_marc[i] && !dr_marc[*it])
                ok=false;

    if(!ok)
        cout<<"NU E SUPORT\n";*/

    cin.close();
    cout.close();
    return 0;
}