#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define per(i,n) for(int i=n;i>=1;--i)
#define pb push_back
#define mp make_pair
#define stack stck  
#define N 7010
#define M 7100
#define inf 1000000007
struct EDGE { int adj, next; } edge[M];
int n, m, top, gh[N];
int dfn[N], low[N], cnt, ind, stop, instack[N], stack[N], belong[N];
void addedge(int x, int y) {
	edge[++top].adj = y;
	edge[top].next = gh[x];
	gh[x] = top;
}
void tarjan(int x) {
	dfn[x] = low[x] = ++ind;
	instack[x] = 1; stack[++stop] = x;
	for (int p=gh[x]; p; p=edge[p].next)
		if (!dfn[edge[p].adj]) {
			tarjan(edge[p].adj);
			low[x] = min(low[x], low[edge[p].adj]);
		} else if (instack[edge[p].adj]) {
			low[x] = min(low[x], dfn[edge[p].adj]);
		}
	if (dfn[x] == low[x]) {
		++cnt; int tmp=0;
		while (tmp!=x) {
			tmp = stack[stop--];
			belong[tmp] = cnt;
			instack[tmp] = 0;
		}
	}
}
pair<int,int> save[M];
set<pair<int,int> > dic; //duplicate edges

namespace flow
{
	struct EDGE { int adj, w, cap, next; } edge[10*M];
	int n, top, gh[2*N], nrl[2*N] , S, T;
	void addedge(int x, int y, int w) {
		//cout<<"fuck: "<<x<<" "<<y<<" "<<w<<endl;
		edge[++top].adj = y;
		edge[top].w = w;
		edge[top].cap=w;
		edge[top].next = gh[x];
		gh[x] = top;
		edge[++top].adj = x;
		edge[top].w = 0;
		edge[top].cap=0;
		edge[top].next = gh[y];
		gh[y] = top;
	}
	int dist[2*N], q[2*N];
	int bfs() {
		memset(dist, 0, sizeof(dist));
		q[1] = S; int head = 0, tail = 1; dist[S] = 1;
		while (head != tail) {
			int x = q[++head];
			for (int p=gh[x]; p; p=edge[p].next)
				if (edge[p].w && !dist[edge[p].adj]) {
					dist[edge[p].adj] = dist[x] + 1;
					q[++tail] = edge[p].adj;
				}
		}
		return dist[T];
	}
	int dinic(int x, int delta) {
		if (x==T) return delta;
		for (int& p=nrl[x]; p && delta; p=edge[p].next)
			if (edge[p].w && dist[x]+1 == dist[edge[p].adj]) {
				int dd = dinic(edge[p].adj, min(delta, edge[p].w));
				if (!dd) continue;
				edge[p].w -= dd;
				edge[p^1].w += dd;
				return dd;
			}
		return 0;
	}
	int work() {
		int ans = 0;
		while (bfs()) {
			memcpy(nrl, gh, sizeof(gh));
			int t; while (t = dinic(S, 2147483647)) ans += t;
		}
		return ans;
	}
}

int col[N],nxt[N],du[N];
int flowedge[M];
vector<pair<int,int> > G[2*N];
vector<int> le,ri;
void dfs(int x)
{
	while (!G[x].empty())
	{
		int i=G[x].size()-1;
		G[x][i].second--;
		int y=G[x][i].first;
		if (G[x][i].second==0)G[x].pop_back();
		if (x==flow::S)le.pb(y);
		if (y==flow::T)ri.pb(x);
		dfs(y);
		return;
	}
}
int main()
{
	//freopen("1.in","r",stdin);
	cin>>n>>m;
	rep(i,m)
	{
		scanf("%d%d",&save[i].first,&save[i].second);
		addedge(save[i].first,save[i].second);
	}
	
	//SCC
	rep(i,n)if (!dfn[i])tarjan(i);
	//Flow
	flow::top=1; 
	flow::S=0; 
	flow::T=2*cnt+1;
	rep(i,cnt)
	{
		flow::addedge(flow::S,i,1);
		flow::addedge(cnt+i,i,inf);
		flow::addedge(cnt+i,flow::T,1);
	}
	dic.clear();
	rep(i,m)flowedge[i]=-1;
	rep(i,m)
		if (belong[save[i].first]!=belong[save[i].second])
		{
			int x=belong[save[i].first];
			int y=belong[save[i].second];
			if (dic.find(mp(x,y))!=dic.end())continue;
			dic.insert(mp(x,y));
			flow::addedge(x,cnt+y,inf);
			flowedge[i]=flow::top;
		}
	int f=flow::work(); //cout<<f<<endl;
	for(int i=flow::S;i<=flow::T;i++)
		for(int p=flow::gh[i];p;p=flow::edge[p].next)
			if (flow::edge[p].cap)
			{
				if (flow::edge[p].cap==flow::edge[p].w)continue;
				G[i].pb(mp(flow::edge[p].adj,flow::edge[p].cap-flow::edge[p].w));
			}
	//for(int i=flow::S;i<=flow::T;i++)
	//	for(auto p:G[i])cout<<i<<" "<<p.first<<" "<<p.second<<endl;
	
	rep(i,f)dfs(flow::S);
	for(int i=0;i<le.size();i++)nxt[le[i]]=ri[i]-cnt,du[ri[i]-cnt]++;
	cout<<le.size()<<endl;
	//assert(le.size()==f);
	int cur=0;
	rep(i,cnt)
	if (!du[i])
	{
		++cur;
		int p=i;
		while (p!=0)col[p]=cur,p=nxt[p];
	}
	rep(i,n)printf("%d ",col[belong[i]]);
	puts("");

	return 0;
}