#include<bits/stdc++.h>
using namespace std;
const int N = 7005;
bitset<N>f[N],tmp;
int n,m;
int dfn[N],low[N],v[N],cnt,tot,fa[N];
stack<int>s;
vector<int>e[N];
vector<int>e1[N];
void tarjan(int x){
	dfn[x] = low[x] = ++tot;
	s.push(x);
	v[x] = 1;
	for(int to:e[x]){
		if(!dfn[to]){
			tarjan(to);
			low[x] = min(low[x],low[to]);
		} else if(v[to]) low[x] = min(low[x],dfn[to]);
	}
	if(low[x] == dfn[x]){
		int y;
		++cnt;
		do{
			y = s.top();
			s.pop();
			fa[y] = cnt;
			v[y] = 0;
		}while(y != x);
	}
}
int match[N];
bool dfs(int x){
	//printf("%d\n",x);
    bitset<N> o = (f[x] & tmp);
    for(int j = o._Find_first();j < o.size();j = o._Find_next(j)){
        tmp[j] = 0;
        if(!match[j] || dfs(match[j])){
            match[j] = x;
            return 1;
        }
    }
    return 0;
}

int c[N],nxt[N],lst[N];
int main(){
	cin >> n >> m;
	for(int i = 1,x,y;i <= m;++i){
		cin >> x >> y;
		e[x].push_back(y);
	}
	for(int i = 1;i <= n;++i) if(!dfn[i]) tarjan(i);
	//printf("QWQ");
	for(int i = 1;i <= n;++i)
		for(int to:e[i]) if(fa[to] != fa[i]) f[fa[i]][fa[to]] = 1;
	for(int i = 1;i <= cnt;++i)
		for(int j = 1;j <= cnt;++j) if(f[j][i]) f[j] |= f[i];
//	for(int i = 0;i <= 50;++i){
//		for(int j = 0;j <= 7000;++j) if(f[i][j]) printf("%d ",j);
//		cout << endl;
//	}	
	//	printf("QWQ");
	tmp.set();
	for(int i = 1;i <= cnt;++i){
		if(dfs(i)) tmp.set();
	}		
	//for(int i = 1;i <= cnt;++i) printf("%d ",match[i]);
	//printf("\n");
	//printf("QWQ");
	int ans = 0;
    for(int i = 1;i <= cnt;i++){
        if(match[i]) {
            nxt[match[i]] = i;
            lst[i] = match[i];
        }
    }
    for(int i = 1;i <= cnt;i++){
        if(!lst[i]){
            int j = i;
            ++ans;
            while(j){
                c[j] = ans;
                j = nxt[j];
            }
        }
    }
    cout << ans << endl;
    for(int i = 1;i <= n;++i) cout << c[fa[i]] << ' ';
	return 0;
}