#include "bits/stdc++.h"
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;
// #define int long long
 
#define dbg_loc() cerr << __PRETTY_FUNCTION__ << " : " << __LINE__ << "\n"
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p){ 
    return os << '(' << p.first << ", " << p.second << ')'; 
}
template<typename T_container,typename T=typename enable_if<!is_same<T_container,string>::value, typename T_container::value_type>::type> 
ostream& operator<<(ostream &os, const T_container &v){ 
    os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; 
}
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ 
    cerr << ' ' << H; 
    dbg_out(T...); 
}
#define LOCAL
#define LOCAL
#ifdef LOCAL 
#define dbg(...) cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl
#else
#define dbg(...)
#endif
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ll mod = (1000000007LL);
inline ll Mod(ll a, ll b){return (a%b);}
inline ll poww(ll a, ll b){ll res = 1;while (b > 0){if(b & 1) res = (res * a)%mod;a = (a * a)%mod;b >>= 1;}return res;}
ll gcd (ll a, ll b) { while (b) { a %= b,swap(a, b);}return a;}
void read(vector<int> &w, int n){w.resize(n);for(int i = 0; i < n; i++) cin>>w[i];}
void print(vector<int> &w){for(int i =0; i < sz(w); i++){if(i == sz(w) - 1) cout<<w[i]<<"\n";else cout<<w[i]<<" ";}}
 
///CUIDADO COM MAXN
#define N 7001 // 1E6

struct SCC{
  vector< vi> g , comps;

  vi val, z, cont, comp;

  int Time =0, ncomps= 0 , n; 

  SCC(vector<vi> g, int n ):n(n) , g(g) , val(n+1,0), comp(n+1, -1) {}
  
  int dfs(int j){
    int low = val[j] = ++Time , x ; z.push_back(j);
    trav(e, g[j]) if(comp[e] < 0)
      low = min(low , val[e] ?: dfs(e));
    if(low == val[j]){
      do{
        x = z.back() ; z.pop_back();
        comp[x] = ncomps;
        cont.push_back(x);
      } while(x != j);
      comps.push_back(cont) , cont.clear();
      ncomps++;
    }
    return val[j] = low;
  }

  void scc(){
    val.assign(n+1,0); comp.assign(n+1,-1);
    Time = ncomps = 0 ;
    rep(i,1,n+1) if(comp[i] < 0 ) dfs(i);
  }
  
  vector<vi> DAG(){// sem arestas repetidas
    vector<vi> dag(n+1);val.assign(n+1,-1);

    for(int i=0;i<ncomps;i++){
      for(auto v : comps[i]){
        for(auto to : g[v]){
          if(val[comp[to]]==-1 && comp[to]!=i){
            val[comp[to]]=1;
            dag[i].pb(comp[to]);
          }
        }
      }
      for(auto v : comps[i])
        for(auto to : g[v])
          val[comp[to]]=-1;
    }
    return dag;
  }
  int repre(int c){
    // representante da componente c (c < ncomps):
    return comps[c][0];
  }
};
int  n,m;
vector<vi> grafo;

struct UF {
	vi e;
	UF(int n) : e(n, -1) {}
	bool sameSet(int a, int b) { return find(a) == find(b); }
	int size(int x) { return -e[find(x)]; }
	int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
	bool join(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) return false;
		if (e[a] > e[b]) swap(a, b);
		e[a] += e[b]; e[b] = a;
		return true;
	}
};

struct Dinic {
	struct Edge {
		int to, rev;
		ll c, oc;
		ll flow() { return max(oc - c, 0LL); } // if you need flows
	};
	vi lvl, ptr, q;
	vector<vector<Edge>> adj;
	Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
	void addEdge(int a, int b, ll c, int rcap = 0) {
		adj[a].push_back({b, sz(adj[b]), c, c});
		adj[b].push_back({a, sz(adj[a]) - 1, rcap, rcap});
	}
	ll dfs(int v, int t, ll f) {
		if (v == t || !f) return f;
		for (int& i = ptr[v]; i < sz(adj[v]); i++) {
			Edge& e = adj[v][i];
			if (lvl[e.to] == lvl[v] + 1)
				if (ll p = dfs(e.to, t, min(f, e.c))) {
					e.c -= p, adj[e.to][e.rev].c += p;
					return p;
				}
		}
		return 0;
	}
	ll calc(int s, int t) {
		ll flow = 0; q[0] = s;
		rep(L,0,31) do { // 'int L=30' maybe faster for random data
			lvl = ptr = vi(sz(q));
			int qi = 0, qe = lvl[s] = 1;
			while (qi < qe && !lvl[t]) {
				int v = q[qi++];
				trav(e, adj[v])
					if (!lvl[e.to] && e.c >> (30 - L))
						q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
			}
			while (ll p = dfs(s, t, LLONG_MAX)) flow += p;
		} while (lvl[t]);
		return flow;
	}
	bool leftOfMinCut(int a) { return lvl[a] != 0; }
};
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    grafo.resize(n+1);
    for(int i =1,a,b; i <= m; i++){
        cin>>a>>b;
        grafo[a].pb(b);
    }

    SCC T = SCC(grafo,n);
    T.scc();

    auto dag = T.DAG();

    UF cu(n+1);

    vi btoa(n + 1, -1), cor(n+1,-1);

    Dinic dinic(2*T.ncomps + 10);
    int src = 0, snk = 2*T.ncomps + 8;
    for(int i = 0; i < T.ncomps; i++){
    	// dbg(i, T.comps[i]);
    	dinic.addEdge(src, i+1, 1);
    	dinic.addEdge(T.ncomps + (i+1), snk, 1);
    	dinic.addEdge(T.ncomps + (i+1), i+1, 1e7);
    	for(auto j: dag[i]){
    		dinic.addEdge(i+1,T.ncomps + (j+1), 1e7);
    	}
    }
    cout<<dinic.calc(src, snk)<<"\n";


    for(int i = 1; i <= T.ncomps; i++){
    	for(int j = 0 ;j < sz(dinic.adj[i]); j++)
    		if(dinic.adj[i][j].to > T.ncomps and dinic.adj[i][j].c < (int)(1e7)){
    			// dbg("join", i-1, dinic.adj[i][j].to-1-T.ncomps);
    			cu.join(i-1, dinic.adj[i][j].to - 1 - T.ncomps);
    		}
    }
    		

    int t=0;
    for(int i = 0; i <= n; i++){
    	int pai = cu.find(i);

    	// dbg(i,pai);
    	if(cor[pai] == -1) cor[pai] = ++t;
    }

    for(int i = 1; i <= n; i++){
    	int cc = cor[  cu.find(T.comp[i]) ];
    	cout<<cc<<" \n"[i==n];
    }

}