program a;
const max=500;
type tradek=array[0..max-1] of integer;
  tboolr=array[0..max-1] of boolean;
var
  prvni:boolean; 
  pagentu,pnegaci,i,j,tym,kdo,koho:integer;
  matrix:array[0..max-1] of tboolr;
  tymy:tradek;
  nesnasi:array[1..3] of tboolr;

procedure nuluj;
var i,j:integer;
begin
  for i:=0 to pagentu-1 do begin
    tymy[i]:=0;
    nesnasi[1,i]:=true;
    nesnasi[2,i]:=true;
    nesnasi[3,i]:=true;
    for j:=0 to pagentu-1 do matrix[i,j]:=true;
  end;
end;

procedure add(koho:integer);
var i:integer;
begin
  for i:=0 to pagentu-1 do
    if not matrix[koho,i] then nesnasi[tym,i]:=false;
end;

begin
  prvni:=true;
  read(pagentu,pnegaci);
  while ((pagentu>0) or (pnegaci>0)) do begin
    if not prvni then writeln
    else prvni:=false;
    nuluj;
    tym:=0;
    for i:=1 to pnegaci do begin
      read(kdo,koho);
      matrix[kdo,koho]:=false;
      matrix[koho,kdo]:=false;
    end;
    for i:=0 to pagentu-1 do begin      
      if (tymy[i]=0) then begin        
        inc(tym);
        if tym=4 then break;
        for j:=0 to pagentu-1 do
          if ((tymy[j]=0) and nesnasi[tym,j]) then begin
            tymy[j]:=tym;
            add(j);
          end;
      end;  
    end;
    if tym>=4 then write('The agents cannot be split')
    else begin
      write(tymy[0]-1);
      for i:=1 to pagentu-1 do write(' ',tymy[i]-1);
    end;
    readln;      
    read(pagentu,pnegaci);
  end;
end.