program teegraafis;
const maxN=100; {Suurim võimalik tippude arv}
var
 N: integer; {Tippude tegelik arv}
 g: array[1..maxN, 1..maxN] of integer; 
   {Graaf ise. Rea ja veeru ristumiskohas
    olev 0 näitab, et serv vastavate nurkade
    vahel puudub, 1 aga, et serv on olemas. 
    Andmed hoitakse sümmeetrilisena. St., et 
    kui tipust a saab tippu b, siis saab ka vastupidi.
    }
  kaugused: array[1..maxN] of integer;
  {Arv näitab, mitmendal sammul vastava
   elemendini jõuti}
  tagasiteed: array[1..maxN] of integer;
   {Arv näitab, millise elemendi(sõlme) kaudu 
   siia jõuti.}
  uurimisjarjekord: array[1..maxN] of integer;
   {Millistest elementidest lähtuvad teid 
    on vaja vaadata.}
  uurimisalgus, uurimisots: integer;
   

procedure tyhjenda;
var
 rida: integer;
 veerg: integer;
begin
  for rida:=1 to N do
    for veerg:=1 to N do
      g[rida, veerg]:=0;
end;

procedure serv(tipp1, tipp2: integer);
{Serva loomine}
begin
  g[tipp1, tipp2]:=1;
  g[tipp2, tipp1]:=1;
end;

procedure kirjuta;
{trükitakse ekraanile iga tipu juurest leitud servad}
var
 rida: integer;
 veerg: integer;
begin
  for rida:=1 to N do begin
    write(rida:5, ':');
    for veerg:=1 to N do
      if g[rida, veerg]=1 then
        write(veerg:3);
    writeln;
  end;
end;

procedure kirjutaMassiiv;
{Ekraanile trükitakse massiivis leiduvad nullid/ühed}
var
  rida, veerg: integer;
begin
  for rida:=1 to N do begin
    for veerg:=1 to N do
      write(g[rida, veerg]:5);
    writeln;
  end;    
end;


function kasServ(tipp1, tipp2: integer): boolean;
{Teatatakse, kas etteantud tippude vahel leidub serv}
begin
  if g[tipp1, tipp2]=1 then kasServ:=true
  else kasServ:=false;
end;

procedure looJuhuServ;
var
  rida, veerg: integer;
begin
 repeat
  rida:=random(N)+1;
  veerg:=random(N)+1;
 until not (kasServ(rida, veerg) or (rida=veerg));
 serv(rida, veerg);
end;

procedure looJuhuGraaf(tippudeArv, servadeArv: integer);
var
  i: integer;
begin
  n:=tippudeArv;
  tyhjenda;
  for i:=1 to servadeArv do
    looJuhuServ;
end;


procedure paigutaServad;
begin
  serv(1, 3);
  serv(3, 5);
end;

procedure alusta;
begin
  randomize;
  N:=10;
  tyhjenda;
  {paigutaServad;}
  looJuhuGraaf(10, 15);
end;

procedure tyhjendaUurimisJarjekord;
begin
  uurimisalgus:=1;
  uurimisots:=0;
end;

procedure lisaUurimisJarjekorda(tipp:integer);
begin
  uurimisots:=uurimisots+1;
  uurimisjarjekord[uurimisots]:=tipp;
end;

function kysiUurimisJarjekorrast: integer;
begin
  kysiUurimisJarjekorrast:=uurimisjarjekord[uurimisalgus];
  uurimisalgus:=uurimisalgus+1;
end;

function kasUurimisJarjekorrasElemente: boolean;
begin
 if uurimisalgus<=uurimisots then
   kasUurimisJarjekorrasElemente:=true
 else
   kasUurimisJarjekorrasElemente:=false;
end;

procedure trykiUurimisJarjekord;
  var
    i: integer;
begin
  for i:=uurimisalgus to uurimisots do
    write(i:3);
  writeln;
end;

procedure arvutaKaugused(tipp: integer);
{Massiivi kaugused leitakse arvud näitamaks
 tippude kaugusi etteantud tipust.}
 var
  i, kaugus, uuritavtipp, vorreldavtipp:integer;
begin
  for i:=1 to n do begin
    kaugused[i]:=-1; {pole külastatud}
    tagasiteed[i]:=-1;
  end;
  kaugus:=0;
  kaugused[tipp]:=kaugus;
  tagasiteed[tipp]:=0; 
    {0 tähendab, et pole enam vaja tagasi minna}
  lisaUurimisJarjekorda(tipp);
  while(kasUurimisJarjekorrasElemente) do begin
    uuritavtipp:=kysiUurimisJarjekorrast;
    kaugus:=kaugused[uuritavtipp];
    for vorreldavTipp:=1 to n do begin
      if kasServ(uuritavTipp, vorreldavTipp) then begin
        if kaugused[vorreldavTipp]=-1 then begin
          lisaUurimisJarjekorda(vorreldavTipp);
          kaugused[vorreldavTipp]:=kaugus+1;
          tagasiteed[vorreldavTipp]:=uuritavTipp;
        end;
      end;
    end
  end;
end; 

procedure leiaLyhimTee(tipp1, tipp2: integer);
var abi:integer;
begin
  arvutaKaugused(tipp1);
  if kaugused[tipp2]>0 then begin
    writeln('Kaugus ', kaugused[tipp2], ' sammu:');
    write(tipp2:3);
    abi:=tagasiteed[tipp2];
    while abi>0 do begin
      write(abi: 3);
      abi:=tagasiteed[abi];
    end;
    writeln;
  end else begin
    writeln('Tipud ', tipp1, ' ja ', tipp2,
      ' pole seotud.');
  end;
end;


begin
  alusta;
  kirjutaMassiiv;
  leiaLyhimTee(1, 5);
  writeln;
end.