#include <bits/stdc++.h>

using namespace std;

const int MAXN = 8200;

vector< int > gr[MAXN];
int l[MAXN];
int r[MAXN];
int cl[MAXN];
int cr[MAXN];
int viz[MAXN];

int step = 1;

int matched = 0;
bool cuplaj(int node) {
  if(viz[node] == step) return false;

  viz[node] = step;


  for(auto &x : gr[node]) {
    if(!r[x] || cuplaj(r[x])) {
      if(!r[x]) matched ++;
      r[x] = node;
      l[node] = x;
      return true;
    }
  }

  return false;
}

void dfs(int node) {
  for(auto &x : gr[node]) {
    if(!cr[x]) {
      cr[x] = 1;
      cl[r[x]] = 0;
      dfs(r[x]);
    }
  }
}

int main() {
	#ifndef INFOARENA
		freopen("input", "r", stdin);
	#else
		freopen("felinare.in", "r", stdin);
		freopen("felinare.out", "w", stdout);
	#endif
	int n, m;
    cin >> n >> m;

    for(int i = 0; i < m; ++i) {
      int a, b;
      cin >> a >> b;
      gr[a].emplace_back(b);
    }

    for(bool ok = true; ok; ++step) {
      ok = false;
      for(int i = 1; i <= n; ++i) {
        if(!l[i]) ok |= cuplaj(i);
      }
    }

    for(int i = 1; i <= n; ++i) {
        if(l[i]) cl[i] = 1;
    }
    for(int i = 1; i <= n; ++i) {
      if(!l[i]) dfs(i);
    } 

    cout << 2*n - matched << '\n';
    for(int i = 1; i <= n; ++i) {
      cout << 3 - cl[i] - cr[i]*2 << '\n';
    }
}