program p32;
const
  maxn	= 500;        { maximální rozměr šachovnice }
  maxv	= 2*maxn;     { max. počet vrcholů grafu }
  maxm	= maxn*maxn;  { max. počet hran grafu }
var
  n, m, k : Integer;  { počet vrcholů hran; max. stupeň }
  edge : array[1..maxm] of record             { jednotlivé hrany }
                color: Integer;                   { barva hrany }
                vert : array[1..2] of Integer;    { krajní vrcholy }
	    end;
  inc  : array[1..maxv, 1..maxn] of Integer;  { inc[v,b] = hrana barvy `b'
                                                u vrcholu `v' }
  ec   : array[1..maxv] of Integer;           { stupně vrcholů }

procedure uncolor(e :Integer);                { odbarví hranu }
var v : Integer;
begin
   for v:= 1 to 2 do
      inc[edge[e].vert[v], edge[e].color] := 0;
end;

procedure color(e, c :Integer);               { obarví hranu }
var v : Integer;
begin
   edge[e].color := c;
   for v:= 1 to 2 do
      inc[edge[e].vert[v], c] := e;
end;

procedure recolor(v, remc, addc	:Integer);    { přebarví cestu }
var e, other : Integer;
begin
  if inc[v][remc] > 0 then
  begin
     e := inc[v, remc];
     uncolor(e);

     other := edge[e].vert[1];
     if other = v then other := edge[e].vert[2];
     recolor(other, addc, remc);

     color(e, addc);
  end;
end;

var i, j, remc, addc, x, y : Integer;
    colored : Boolean;
begin
   Readln(n, m);                              { načteme vstup }
   for i:= 1 to m do
   begin
      Readln(x, y);
      edge[i].vert[1] := x;
      edge[i].vert[2] := y+n;
      ec[x] := ec[x]+1;
      ec[y+n] := ec[y+n]+1;
   end;

   k := 0;                                    { zjistíme max. stupeň }
   for i:= 1 to 2*n do
      if ec[i] > k then
	 k := ec[i];

   for i:= 1 to m do                          { postupně přidáváme hrany }
   begin
      colored := false;
      for j:= 1 to k do                       { je ji možno obarvit rovnou? }
	 if (inc[edge[i].vert[1], j] = 0) and (inc[edge[i].vert[2], j] = 0) then
	 begin
	    color(i, j);
	    colored := true;
	    break;
	 end;

      if colored then continue;

      for j:= 1 to k do                       { hledáme volné barvy }
	 if (inc[edge[i].vert[1], j] = 0) and (inc[edge[i].vert[2], j] > 0) then
	 begin
	    addc := j;
	    break;
	 end;
      for j:= 1 to k do
	 if (inc[edge[i].vert[1], j] > 0) and (inc[edge[i].vert[2], j] = 0) then
	 begin
	    remc := j;
	    break;
	 end;

      recolor(edge[i].vert[1], remc, addc);   { přebarvíme cestu }
      color(i, remc);                         { a obarvíme novou hranu }
   end;

   Writeln(k);                                { už jen vypsat výstup }
   for i:= 1 to m do
      Writeln(edge[i].color);
end.