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,k,m,t,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;

function kolik(koho:integer):integer;
var i,p:integer;
begin
  p:=0;
  for i:=0 to pagentu-1 do
    if nesnasi[tym,i] and matrix[koho,i] then inc(p);
  kolik:=p;
end;

function muzupridat:integer;
var i:integer;
begin
  i:=0;
  while ((i<pagentu) and (not((nesnasi[tym,i]) and (tymy[i]=0)))) do inc(i);
  if i>=pagentu then begin
    muzupridat:=-1;
    writeln('nemuzu pridat'); end
  else begin
    muzupridat:=i;
    writeln('muzu pridat');end;
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;
        while (muzupridat>-1) do begin
          m:=0;
          t:=0;
          for j:=0 to pagentu-1 do if tymy[j]=0 then begin
            k:=kolik(j);
            if k>m then begin
              m:=k;
              t:=j; end;
          end;
          writeln('pridavam ',t,'do',tym);
          add(t);
          tymy[t]:=tym;
        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.