program KSP945;

const MAXN = 100;                      { Maximalni pocet vrcholu }

{ Pozn: cislovani mest je od 1..N. Konverze se provadi pri nacitani }

var N : integer;                       { pocet hran }
    Hrana : array [1..MAXN, 1..MAXN] of boolean; { udava pritomnost hran }
    MinRez : integer;                  { udava velikost zatim nejmensiho rezu }
    i,p : integer;                     { pomocna promenna }

    tok : array [1..MAXN, 1..MAXN] of integer; { pomocne pole pro NajdiMinRez }
                                       { udava aktualni tok }

function NajdiMinRez(z,s:integer) : integer;
{ Nalezne velikost maximalniho toku v grafu se zdrojem 'z' a spotrebicem 's' }
var i,j : integer;   { pomocne promenne }
    fronta : array [1..MAXN] of integer;  { fronta vrcholu pro prohledavani do sirky }
    ffirst, flast : integer;   { predek a zadek fronty }
    cesta : array [1..MAXN] of integer; { udava, odkud jsme navstivili dany vrchol }
    velikosttoku : integer;   { udava velikost max. toku, tj. pocet iteraci algoritmu }
begin
   for i:=1 to N do
     for j:=1 to N do tok[i,j]:=0;

   velikosttoku := 0;

   while true do
    begin
       { hleda zlepsujici cestu pruchodem do sirky }
       ffirst := 1;
       flast  := 1;
       fronta[1] := z;   { zdroj dame do fronty }

       for i:=1 to N do cesta[i]:=0;
       cesta[z] := MAXN + 1;

       while ffirst <= flast do
        begin
           j := fronta[ffirst]; inc(ffirst);   { vezmi prvni prvek z fronty }
           for i:=1 to N do
             if Hrana[j,i] and (tok[j,i] <= 0) and (cesta[i] = 0) then
                    { jdu po nevyuzite, nebo proti proudu do nenavstiveneho }
              begin
                 cesta[i] := j;                   { do 'i' prijdu z 'j' }
                 inc(flast); fronta[flast] := i;  { zarad do fronty }
              end;
           if cesta[s]<>0 then ffirst:=flast+1;
	       { kdyz jsme dosahli spotrebice, nasilne ukonci }
        end;

       if cesta[s]=0 then   { nenasli jsme zlepsujici cestu ke spotrebice }
        begin
           NajdiMinRez := velikosttoku;
           exit;            { tok jiz nelze dale zlepsovat }
        end;

       inc(velikosttoku);
       { aktualizuj tok podle zlepsujici cesty }
       i:=s;
       while cesta[i] <> MAXN + 1 do
        begin
           inc(tok[cesta[i],i]); dec(tok[i,cesta[i]]);
           i:=cesta[i];
        end;
    end;
end;

procedure vstup; { nacte graf }
var i,j : integer;
begin
   write('Zadej pocet vrcholu :'); read(n);
   for i:=1 to n do
    for j:=1 to n do hrana[i,j]:=false;
   writeln('Zadavej jednotlive hrany. 0 0 ukonci');
   repeat
     read(i,j);
     if (i<>0) or (j<>0) then begin hrana[i+1,j+1]:=true; hrana[j+1,i+1]:=true; end;
   until (i=0) and (j=0);
end;

begin
   vstup;
   MinRez := n;
   for i:=2 to n do    { Pro zdroj = '1' a vsechna ostatni mesta jako spotrebice }
    begin
       p:=NajdiMinRez(1,i);
       if p<MinRez then MinRez := p;
    end;
   writeln('Silnicari mohou nechat rozpadnout ',MinRez - 1,' silnice');
end.