#include <cstdio>

#include <vector>

#include <bitset>

using namespace std;


void dfff(int node,int sgn,int fr)

{

    int ok[505];

    for(int i=1;i<=node;++i)

    for(int j=node+1;j<=2*node;++j)

    if(ok[i]==ok[j])

    {

        ok[i]=sgn;

        dfff(i,1-sgn,fr);

        ok[j]=fr;

        dfff(j,sgn,1-fr);

    }

    return;

}

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;

}