program trpaslici;
const MAXN=100;
var nesnasi_kolik: array[1..MAXN] of word; 
      { Kolik trpaslíků nesnáší i-tý trpaslík? }
    nesnasi_koho: array[1..MAXN,1..MAXN] of word;
      { Které trpaslíky nesnáší i-tý trpaslík? }
    skupina: array[1..MAXN] of word;
      { Do které skupiny patří i-tý trpaslík? }
    skupin_rozdily: array[1..MAXN] of integer;
      { Velikosti rozdílů velikostí skupin v jednotlivých dvojicích }
    deficit: array[-MAXN..MAXN] of integer;
      { Kterých deficitů lze dosáhnout?
        = -1 ... nelze
	=  0 ... lze dosáhnout bez invertování
        >  0 ... pořadí poslední invertované dvojice skupin trpaslíků }
    holic: array[1..MAXN] of byte;
      { Ke kterému holiči půjde i-tý trpaslík? }
    N: word;
      { Počet trpaslíků }
    L: word;
      { Počet dvojic skupin }
procedure nacti_vstup;
  var M:word;
      i,j,k:word;
  begin
    readln(N,M);
    for k:=1 to N do nesnasi_kolik[k]:=0;
    for k:=1 to M do
      begin
        readln(i,j);
	inc(nesnasi_kolik[i]); nesnasi_koho[i][nesnasi_kolik[i]]:=j;
	inc(nesnasi_kolik[j]); nesnasi_koho[j][nesnasi_kolik[j]]:=i;
      end
  end;
function urci_skupiny: boolean;
  { Vrací false, pokud rozdělení neexistuje. }
  function zarad(trpaslik, do_skupiny: word; k_holici: byte): boolean;
    { Vrací false, pokud rozdělení neexistuje. }
    var i: word;
    begin
      skupina[trpaslik]:=do_skupiny;
      holic[trpaslik]:=k_holici;
      zarad:=false; { Default }
      for i:=1 to nesnasi_kolik[trpaslik] do
        begin
          if skupina[nesnasi_koho[trpaslik][i]]=0 then
	    if not zarad(nesnasi_koho[trpaslik][i],do_skupiny,3-k_holici) then
	      exit;
          if skupina[trpaslik]<>skupina[nesnasi_koho[trpaslik][i]] then
	    halt(1); { Chyba v programu ;( }
          if holic[trpaslik]=holic[nesnasi_koho[trpaslik][i]] then
	    exit; { Nelze rozdelit }
	end;
      zarad:=true	
    end;
  var k :word;
  begin
    for k:=1 to N do skupina[k]:=0;
    L:=0; { Číslo poslední vytvořené skupiny }
    urci_skupiny:=false; { Default }
    for k:=1 to N do
      if skupina[k] = 0 then
        begin
	  inc(L);
          if not zarad(k,L,1) then exit;
	end;
    urci_skupiny:=true;
    for k:=1 to L do skupin_rozdily[k]:=0;
    for k:=1 to N do
      if holic[k]=1 then
        inc(skupin_rozdily[skupina[k]])
      else
        dec(skupin_rozdily[skupina[k]])
  end;
procedure rozdel_trpasliky;
  var i,j:integer;
  begin
    for i:=-N to N do deficit[i]:=-1;
    j:=0;
    for i:=1 to L do j:=j+skupin_rozdily[i];
    deficit[j]:=0;
    for i:=1 to L do
      for j:=-N to N do  
        if (deficit[j]<>-1) and (deficit[j]<>i) and 
	   (deficit[j-2*skupin_rozdily[i]]=-1) then
	  deficit[j-2*skupin_rozdily[i]]:=i;
    j:=0;	  
    for i:=N downto 0 do
      begin
        if deficit[i]<>-1 then j:=i;
        if deficit[-i]<>-1 then j:=-i;
      end;	
    while deficit[j]<>0 do
      begin
        for i:=1 to N do
	  if skupina[i]=deficit[j] then
	    holic[i]:=3-holic[i];
        j:=j+2*skupin_rozdily[deficit[j]];
      end;
  end;
procedure vypis_vystup;
  var i:word;
  begin
    writeln('K prvnímu holiči:');
    for i:=1 to N do if holic[i]=1 then write(i,' ');
    writeln;  
    writeln('K druhému holiči:');
    for i:=1 to N do if holic[i]=2 then write(i,' ');
    writeln;  
  end;
begin
  nacti_vstup;
  if not urci_skupiny then 
    writeln('Trpaslíky nelze rozdělit mezi holiče!');
  rozdel_trpasliky;
  vypis_vystup;
end.