program BipartitniGraf;
{Rozdeleni mest do dvou skupin - bipartitni graf}

const MaxN=100;                 {maximalni mozny pocet mest}

var A:array[1..MaxN,1..MaxN] of boolean;     {matice silnic}
    Barva:array[1..MaxN] of -1..1;          {rozdeleni mest}
    Zasob:array[1..MaxN] of 1..MaxN;  {pracovni seznam mest}
    Vrchol:0..MaxN;         {index posledniho prvku seznamu}
    N:1..MaxN;              {skutecny pocet mest}
    Zarazena:integer;       {pocet mest zarazenych do skupin}
    Konflikt:Boolean;       {mesta nelze rozdelit}
    i,j:integer;

begin

{Inicializace promennych a nacteni vstupnich dat:}
write('Pocet mest: ');
readln(N);
for i:=1 to N do
  begin
  for j:=1 to N do A[i,j]:=false;
  Barva[i]:=0
  end;
write('Seznam vsech silnic');
writeln(' - dvojici cisel mest ODKUD a KAM vede:');
while not eof do
  begin
  read(i,j);
  A[i,j]:=true;
  A[j,i]:=true    {silnice jsou obousmerne}
  end;

{Rozdelovani mest:}
Zasob[1]:=1;    {vychozi mesto}
Vrchol:=1;      {v seznamu zarazenych je zatim samo}
Barva[1]:=1;    {zarazeno do skupiny 1}
Zarazena:=1;    {jedno mesto je zarazeno}
Konflikt:=false;
while (Vrchol>0) and not Konflikt do
  begin
  j:=Zasob[Vrchol];       {odebrat cislo ze zasobniku}
  Vrchol:=Vrchol-1;
  for i:=1 to N do
    if A[i,j] then        {vede silnice z j do i}
      if Barva[i]=0 then
        begin             {obarvit mesto i}
        Barva[i]:=-Barva[j];
        Vrchol:=Vrchol+1;
        Zasob[Vrchol]:=i;
        Zarazena:=Zarazena+1  {dalsi mesto zarazeno}
        end
      else if Barva[i]=Barva[j] then
        Konflikt:=true;   {doslo ke kolizi - nelze rozdelit}
  if (Vrchol=0) and (not Konflikt) and (Zarazena<N) then
    begin
    {Zasobnik je prazdny, ale jeste nebyla obarvena
     vsechna mesta ani nedoslo ke konfliktu.
     Libovolne dosud nezarazene mesto muzeme zaradit
     do kterekoliv skupiny -> prvni dosud nezarazene
     dame do skupiny 1}
    j:=1;
    while Barva[j]<>0 do j:=j+1;
    Zasob[1]:=j;             {nove zarazene mesto}
    Vrchol:=1;               {v seznamu zarazenych je samo}
    Barva[j]:=1;             {zarazeno do skupiny 1}
    Zarazena:=Zarazena+1;    {dalsi mesto je zarazeno}
    end
  end;

{Vyhodnoceni procesu rozdelovani mest:}
if Konflikt then
  writeln('Rozdeleni mest do dvou skupin neexistuje.')
else
  begin
  writeln('Rozdeleni mest do dvou skupin je mozne.');
  writeln('Jedno takove pripustne rozdeleni vypada takto:');
  write('1.skupina:');
  for i:=1 to N do
    if Barva[i]=1 then write(i:3);
  writeln;
  write('2.skupina:');
  for i:=1 to N do
    if Barva[i]=-1 then write(i:3);
  writeln
  end

end.