#include <bits/stdc++.h>

using namespace std;

ifstream fin( "felinare.in" );
ofstream fout( "felinare.out" );

const int DIM = 16500;

vector<int> G[DIM];
vector<pair<int, int>> res;
int L[DIM], R[DIM];
bool viz[DIM];

bool pair_up( int u ) {
  if ( viz[u] ) return false;
  viz[u] = true;
  for ( auto v : G[u] ) {
    if ( !R[v] ) {
      L[u] = v;
      R[v] = u;
      return true;
    }
  }
  for ( auto v : G[u] ) {
    if ( pair_up(R[v]) ) {
      L[u] = v;
      R[v] = u;
      return true;
    }
  }
  return false;
}

vector<int> newG[DIM];
bool ok[DIM];

void dfs( int u ) {
  viz[u] = true;
  for ( auto v : newG[u] ) {
	if ( !viz[v] ) {
	  dfs(v);
	}
  }
}

int main() {
  int n, m, e, u, v;

  fin >> n >> m;
  while ( m-- ) {
    fin >> u >> v;
    G[u].push_back(n + v);
  }
  bool ok = true;
  while ( ok ) {
    ok = false;
    for ( int i = 1; i <= n; ++i ) {
      viz[i] = false;
    }
    for ( int i = 1; i <= n; ++i ) {
      if ( !L[i] ) {
        if ( pair_up(i) ) ok = true;
      }
    }
  }
  int cnt = 2 * n;
  for ( int i = 1; i <= n; ++i ) {
    viz[i] = false;
	if ( L[i] ) {
	  newG[L[i]].push_back(i);
	  --cnt;
	}
	for ( auto u : G[i] ) {
	  if ( u != L[i] ) {
		newG[i].push_back(u);
	  }
	}
  }
  for ( int i = 1; i <= n; ++i ) {
    if ( !L[i] ) dfs(i);	
  }
  fout << cnt << "\n";
  for ( int i = 1; i <= n; ++i ) {
    if ( viz[i] && !viz[i + n] ) {
      fout << "3\n";
	} else if ( !viz[i] && viz[i + n] ) {
	  fout << "0\n";
	} else if ( viz[i] && viz[i + n] ) {
	  fout << "1\n";
	} else {
	  fout << "2\n";
	}
  }
  fin.close();
  fout.close();
  return 0;
}