#include <bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
using ll=long long;
const int N=7010,M=4*7010;
vector<int> ve[7010];
vector<int> re[7010];
int n,m;
int stk[N],sz[N],scc[N];
int dfn[N]; //时间戳，记录dfs序
int low[N];//追溯值
bool instk[N];
int cnt=0,tot=0,top=0;
void tarjan(int u){
    dfn[u]=low[u]=++tot;
    stk[++top]=u,instk[u]=true;
    for(auto i:ve[u]){
        if(!dfn[i]){
            tarjan(i);
            low[u]=min(low[u],low[i]);
        }
        else if(instk[i])   low[u]=min(low[u],dfn[i]);
    }
    if(dfn[u]==low[u]){
        ++cnt;
        int y;
        do{
            y=stk[top--];
            instk[y]=false;
            scc[y]=cnt;
            sz[cnt]++;
        }while(y!=u);
    }
}
const ll INF=1e18;
struct edge{int v;ll w,pre_w,nxt;}edge[2*M];
int head[2*N],cur[2*N],dep[2*N];
int ctz=1,st,ed;
int pot_sum;
void add(int u,int v,ll w){
    edge[++ctz]={v,w,w,head[u]};
    head[u]=ctz;
    edge[++ctz]={u,0,0,head[v]};
    head[v]=ctz;    
}
bool bfs(){
    copy(head,head+pot_sum+1,cur);
    fill(dep,dep+pot_sum+1,-1);
    queue<int> qe;
    dep[st]=0;qe.push(st);
    while(!qe.empty()){
        int t=qe.front();qe.pop();
        for(int i=head[t];i;i=edge[i].nxt){
            int v=edge[i].v;ll w=edge[i].w;
            if(w>0&&dep[v]==-1){
                dep[v]=dep[t]+1;
                qe.push(v);
            }
        }
    }
    return dep[ed]!=-1;
}
ll dfs(int u=st,ll flow=INF){
    ll rem=flow;
    if(u==ed)   return flow;
    for(int i=cur[u];i&&flow;i=edge[i].nxt){
        cur[u]=i;
        int v=edge[i].v;ll w=edge[i].w;
        if(w>0&&dep[v]==dep[u]+1){
            ll t=dfs(v,min(w,rem));
            rem-=t;
            edge[i].w-=t;
            edge[i^1].w+=t;
        } 
    }
    return flow-rem;
}
ll dinic(){
    ll ans=0;
    while(bfs())    ans+=dfs();
    return ans;
}
int col[N];
// int fa[N];
// int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
// void merge(int u,int v){
//     u=get(u),v=get(v);
//     fa[u]=v;
// }
int c=0;
int color(int u){
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].v,w=edge[i].pre_w-edge[i].w;
        if(v!=st&&v!=ed&&w>0){
            int t=color(v);
            edge[i].w++;
            if(u>cnt)	col[u-cnt]=t;
            else col[u]=t;
            return t;
        }
    }
    if(u>cnt)	u-=cnt; 
    if(!col[u]) col[u]=++c;
    return col[u];  
}
void solve() {
    cin>>n>>m;
    int u,v;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        ve[u].push_back(v);
    } 
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    } 
    st=0,ed=2*cnt+1;
    for(int i=1;i<=cnt;i++){add(0,i,1),add(i+cnt,ed,1),add(i+cnt,i,INF);}
    for(int i=1;i<=n;i++){
        for(auto j:ve[i]){
            if(scc[j]!=scc[i])  add(scc[i],scc[j]+cnt,INF);
        }
    }
    cout<<cnt<<'\n';
    pot_sum=2*cnt+1;
    ll ans=dinic();
    // for(int i=1;i<=cnt;i++) fa[i]=i;   
    for(int i=1;i<=cnt;i++){
        if(col[i])    continue;
        color(i);
    }

    for(int i=1;i<=n;i++)   cout<<col[scc[i]]<<' ';
    cout<<'\n';
}
int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int _ = 1;
    //cin >> _;
    while(_--) solve();
    return 0;
}