#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

#define ll long long
#define MIN(a , b) (((a) < (b)) ? (a) : (b))
#define MAX(a , b) (((a) < (b)) ? (b) : (a))

int const nmax = 8191;
vector<int> g[5 + nmax * 2];
int used[5 + nmax];
int mat[5 + nmax * 2];

bool pairup(int u1){
  used[u1] = 1;

  for(int h = 0 ; h < g[u1].size() ; h++){
    int v1 = g[u1][h];
    if(mat[v1] == 0){
      mat[v1] = u1;
      mat[u1] = v1;
      //cout << u1 << " " << v1 << '\n';

      return 1;
    } else {
      int u2 = mat[v1];
      if(used[u2] == 0){
        if(pairup(u2) == 1){
          mat[v1] = u1;
          mat[u1] = v1;
          //out << u1 << " " << v1 << '\n';
          return 1;
        }
      }
    }
  }
  return 0;
}

int maxmatch(int n){
  int result = 0;

  while(true) {
    for(int i = 1 ; i <= n ; i++)
      used[i] = 0;
    bool ok = 0;

    for(int i = 1 ; i <= n ; i++){
      if(mat[i] == 0 && pairup(i) == 1) {
        //cout << ":" << i << ":" << '\n';
        ok = 1;
        result++;
      }
    }

    if(ok == 0)
      break;
  }
  return result;
}

int seen[5 + nmax];

void dfs(int node , int n){
  if(seen[node] == 0){
    seen[node] = 1;

    if(node <= n){
      for(int h = 0 ; h < g[node].size() ; h++)
        dfs(g[node][h] , n);
    } else {
      if(0 < mat[node])
        dfs(mat[node] , n);
    }
  }
}

void minimumcover(int n){

  for(int i = 1 ; i <= n ; i++){
    if(mat[i] == 0)
      dfs(i , n);
  }
  for(int i = 1 ; i <= n ; i++){
    //cout << seen[i] << " " << seen[i] << '\n';

    int result = 3;

    if(seen[i] == 0)
      result --;
    if(seen[i + n] == 1)
      result -= 2;

    out << result << '\n';
  }
}

int main()
{
  int n , m;
  in >> n >> m;
  for(int i = 1 ; i <= m ; i++){
    int x , y;
    in >> x >> y;
    g[x].push_back(y + n);
    //cout << x << " " << y + n << '\n';
  }

  out << n * 2 - maxmatch(n) << '\n';
  minimumcover(n);

  return 0;
}