#include <bits/stdc++.h>
using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
const int NMAX=8200;

int n,ans,type[3];
short sol[NMAX][2];
bool used[NMAX][2];
bool fused[NMAX];
vector <int> l[NMAX],r[NMAX];

void dfs(int,int,int);
void calc(int,int,int);

int main(){
    int i,m,x,y;
    bool ok=1;
    fin>>n>>m;
    for(i=0;i<m;++i){
        fin>>x>>y;
        l[x].push_back(y);
        r[y].push_back(x);
    }
    ans=2*n;
    for(i=1;i<=n;++i){
        if(!fused[i]){
            type[0]=type[1]=0;
            dfs(i,0,0);
            calc(i,((type[1]<type[0]) ? 1:0),0);
        }
    }

    fout<<ans<<'\n';
    for(i=1;i<=n;++i)
        fout<<3-sol[i][0]-sol[i][1]<<' ';
    return 0;
}
void dfs(int node,int tip,int part){
    fused[node]=1;
    used[node][part]=1;
    ++type[tip];
    sol[node][part]=tip;
    if(!part){
        for(auto it:l[node]){
            if(!used[it][1])
                dfs(it,!tip,!part);
        }
    }else{
        for(auto it:r[node]){
            if(!used[it][0])
                dfs(it,!tip,!part);
        }
    }
}
void calc(int node,int tip,int part){
    used[node][part]=0;
    if(!part){
        if(sol[node][part] == tip){
            sol[node][part]=1;
            --ans;
        }else
            sol[node][part]=0;
        for(auto it:l[node]){
            if(used[it][1])
                calc(it,tip,!part);
        }
    }else{
        if(sol[node][part] == tip){
            sol[node][part]=2;
            --ans;
        }else
            sol[node][part]=0;
        for(auto it:r[node]){
            if(used[it][0])
                calc(it,tip,!part);
        }
    }
}