#include<bits/stdc++.h>
#define NMAX 8191

using namespace std;

ifstream fi("felinare.in");
ofstream fo("felinare.out");

int n,m,x,y;
vector<int> G[NMAX+5];
vector<int> GT[NMAX+5];
int felinare[NMAX+5][3];
int felinare_final[NMAX+5][3];
queue<pair<int,int>> q;
int cnttot, cntap,rez;

void bf(int snod,int tip){
    felinare[snod][tip]=1;
    q.push(make_pair(snod,tip));
    int nod,newnod;
    while(!q.empty()){
        nod=q.front().first;
        tip=q.front().second;
        q.pop();
        cnttot++;
        cntap+=felinare[nod][tip];
        if(tip==1){
            for(int i=0;i<G[nod].size();i++){
                newnod=G[nod][i];
                if(felinare[newnod][2]==-1){
                    felinare[newnod][2]=1-felinare[nod][1];
                    q.push(make_pair(newnod,2));
                }
            }
        }else{
            for(int i=0;i<GT[nod].size();i++){
                newnod=GT[nod][i];
                if(felinare[newnod][1]==-1){
                    felinare[newnod][1]=1-felinare[nod][2];
                    q.push(make_pair(newnod,1));
                }
            }
        }
    }
}

void bf_final(int snod,int tip,int val){
    felinare_final[snod][tip]=val;
    q.push(make_pair(snod,tip));
    int nod,newnod;
    while(!q.empty()){
        nod=q.front().first;
        tip=q.front().second;
        q.pop();
        if(tip==1){
            for(int i=0;i<G[nod].size();i++){
                newnod=G[nod][i];
                if(felinare_final[newnod][2]==-1){
                    felinare_final[newnod][2]=1-felinare_final[nod][1];
                    q.push(make_pair(newnod,2));
                }
            }
        }else{
            for(int i=0;i<GT[nod].size();i++){
                newnod=GT[nod][i];
                if(felinare_final[newnod][1]==-1){
                    felinare_final[newnod][1]=1-felinare_final[nod][2];
                    q.push(make_pair(newnod,1));
                }
            }
        }
    }
}

int main(){
    fi>>n>>m;
    for(int i=1;i<=m;i++){
        fi>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        felinare[i][1]=felinare[i][2]=-1;
        felinare_final[i][1]=felinare_final[i][2]=-1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=2;j++){
            if(felinare[i][j]==-1){
                cnttot=cntap=0;
                bf(i,j);
                if(cntap>cnttot-cntap){
                    bf_final(i,j,1);
                    rez+=cntap;
                }else{
                    bf_final(i,j,0);
                    rez+=(cnttot-cntap);
                }
            }
        }
    }
    fo<<rez<<'\n';
    for(int i=1;i<=n;i++){
        fo<<felinare_final[i][1]+2*felinare_final[i][2]<<'\n';
    }
    fi.close();
    fo.close();
}