#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 8191;
const int DIM = 1000000;

int n, m, res, pos;
int match[1 + 2 * NMAX];
int dist[1 + 2 * NMAX];
bool vis[1 + 2 * NMAX];
bool s[1 + 2 * NMAX];
char buff[DIM];

vector < int > g[1 + 2 * NMAX];
string output;

void addedge(int x, int y){
  g[x].push_back(y);
  g[y].push_back(x);
}

int read(int & nr){
  nr = 0;

  while(!isdigit(buff[pos]))
    if(++pos == DIM){
      in.read(buff, DIM);
      pos = 0;
    }

  while(isdigit(buff[pos])){
    nr = nr * 10 + (buff[pos] - '0');

    if(++pos == DIM){
      in.read(buff, DIM);
      pos = 0;
    }
  }
}

void bfs(){
  fill(dist + 1, dist + n + 1, -1);
  queue < int > q;
  for(int i = 1; i <= n; i++){
    if(match[i] <= 0){
      q.push(i);
      dist[i] = 0;
    }
  }

  while(!q.empty()){
    int u1 = q.front();
    q.pop();
    for(int i = 0; i < g[u1].size(); i++){
      int v1 = g[u1][i];
      int u2 = match[v1];
      if(0 < u2 && dist[u2] < 0){
        dist[u2] = dist[u1] + 1;
        q.push(u2);
      }
    }
  }
}

bool dfs(int u1){
  vis[u1] = true;
  for(int i = 0; i < g[u1].size(); i++){
    int v1 = g[u1][i];
    int u2 = match[v1];
    if(u2 <= 0){
      match[v1] = u1;
      match[u1] = v1;
      return true;
    } else if(vis[u2] == 0 && dist[u2] == dist[u1] + 1){
      if(dfs(u2) == true){
        match[v1] = u1;
        match[u1] = v1;
        return true;
      }
    }
  }
  return false;
}

void maxmatching(){
  int answer = 0;
  int add = 1;

  while(0 < add){
    bfs();
    fill(vis + 1, vis + n + 1, false);
    add = 0;
    for(int i = 1; i <= n; i++){
      if(match[i] <= 0){
        if(dfs(i) == true)
          add++;
      }
    }
    answer += add;
  }
  //cout << answer << '\n';
  //for(int i = 1; i <= n; i++)
  //  cout << match[i] << ' ';
}

void solve(int is)
{
  for(int j = 0; j < g[is].size(); j++){
    int jd = g[is][j];
    if(s[jd] == false){
      s[jd] = true;
      s[match[jd]] = false;
      solve(match[jd]);
    }
  }
}

int main()
{
  //in >> n >> m;
  read(n);
  read(m);
  int x, y;
  for(int i = 1; i <= m; i++){
    //int x, y;
    //in >> x >> y;
    read(x);
    read(y);
    addedge(x, y + n);
  }

  maxmatching();

  for(int i = 1; i <= n; i++){
    if(0 < match[i]){
      s[i] = true;
    }
  }

  for(int i = 1; i <= n; i++){
    if(match[i] <= 0){
      solve(i);
    }
  }

  for(int i = 1; i <= n; i++){
    if(s[i] == true){
      if(s[i + n] == true){
        output += "0\n";
        res += 0;
      }
      else if(s[i + n] == false){
        output += "2\n";
        res ++;
      }
    } else if(s[i] == false){
      if(s[i + n] == true){
        output += "1\n";
        res++;
      }
      else if(s[i + n] == false){
        output += "3\n";
        res += 2;
      }
    }
  }

  out << res << '\n' << output;

  in.close();
  out.close();
  return 0;
}