#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];
int st_grad[NMAX];
int dr_grad[NMAX];

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;
}

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++;

    for(int i=1;i<=n;i++)
        if(st[i])
            for(vector<int>::iterator it=graf[i].begin();it!=graf[i].end();it++)
                if(!dr[*it])
                    st_grad[i]++;

    for(int i=1;i<=n;i++)
        if(dr[i])
            for(vector<int>::iterator it=graf_inv[i].begin();it!=graf_inv[i].end();it++)
                if(!st[*it])
                    dr_grad[i]++;

    for(int i=1;i<=n;i++)
        if(st[i]){
            int vec=st[i];

            //cout<<i<<' '<<vec<<endl;
            //cout<<st_grad[i]<<' '<<dr_grad[vec]<<endl;

            if(st_grad[i]){
                //cout<<"1\n";
                st[i]=1,dr[vec]=0;
            }
            else if(dr_grad[vec]){
                //cout<<"2\n";
                dr[vec]=1,st[i]=0;
            }
            else{
                //cout<<"1\n";
                st[i]=1,dr[vec]=0;
            }
        }


    cout<<2*n-cuplaj<<'\n';

    for(int i=1;i<=n;i++){
        st[i]=1-st[i];
        dr[i]=1-dr[i];

        cout<<((dr[i]<<1)+st[i])<<'\n';
    }

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