#include <cstdio>
#include <vector>
#include <bitset>
using namespace std;

bitset<8191> used, MinCoverLeft, MinCoverRight;
vector<vector<int>> Graph;
vector<int> Left, Right;

bool makeMatch(int k)
{
  if (used[k])
    return false;
  used[k] = true;
  for (auto v: Graph[k])
    if (Left[v] == -1) {
      Right[k] = v;
      Left[v] = k;
      return true;
    }
  for (auto v: Graph[k])
    if (makeMatch(Left[v])) {
      Right[k] = v;
      Left[v] = k;
      return true;
    }
  return false;
}

void checkFix(int k)
{
  for (auto v: Graph[k])
    if (!MinCoverRight[v]) {
      MinCoverRight[v] = true;
      MinCoverLeft[Left[v]] = false;
      checkFix(Left[v]);
    }
}

int main()
{
  freopen("felinare.in", "r", stdin);
  freopen("felinare.out", "w", stdout);

  int N, M;
  scanf("%d%d", &N, &M);

  Graph.resize(N);
  Left.resize(N);
  Right.resize(N);
  fill(Left.begin(), Left.end(), -1);
  fill(Right.begin(), Right.end(), -1);

  for (int i = 0; i < M; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    --l; --r;
    Graph[l].emplace_back(r);
  }
  int matches = 0;
  bool madeProgress = true;
  while (madeProgress) {
    used = 0;
    madeProgress = false;
    for (int i = 0; i < N; ++i)
      if (Right[i] == -1 && makeMatch(i)) {
	madeProgress = true;
	++matches;
      }
  }
  printf("%d\n", 2*N - matches);
  
  for (int i = 0; i < N; ++i)
    if (Right[i] != -1) // If it is in the match
      MinCoverLeft[i] = true;

  for (int i = 0; i < N; ++i)
    if (Right[i] == -1) // If it is not in the match
      checkFix(i);

  for (int i = 0; i < N; ++i)
    if (MinCoverLeft[i] && MinCoverRight[i])
      printf("0\n");
    else if (MinCoverLeft[i])
      printf("2\n");
    else if (MinCoverRight[i])
      printf("1\n");
    else
      printf("3\n");
  
  return 0;
}