Program grafo ;
var
 matriz: array [1..10,1..10] of integer;
 matriz2: array [1..10,1..10] of integer;
 matrizaux: array[1..10,1..10] of integer;
 matrizaux2: array[1..10,1..10] of integer;
 i,j,n,d,e,k,f,g:integer;
 nome: array [1..10] of string;
 resp, resp2, resp3:char;
Begin
   writeln ('Favor entrar com o numero de rotulos dos vertices');
   readln(n);
   if n>10 then
   begin
     writeln ('Erro. O maximo de rotulos e 10 e o minimo e 2');
   end
   else
   begin
   if n>1 then
   begin
       for i:=1 to n do
       begin
             writeln ('Entre com o rotulo ',i);
             readln (nome [i]);
      end;
       for i:=1 to n do
       begin
         for j:=1 to n do
         begin
         if i<j then
             begin
             if i<>j then
             begin
               writeln (nome[i],' conhece ',nome[j],'? (s,n)');
               readln (resp);
               if resp='s' then
               begin
                 matriz[i,j]:=1;
                 matriz[j,i]:=1;
               end
               else
               begin
                 matriz[i,j]:=0;
                 matriz[j,i]:=0;
               end;
             end
            else
            begin
            matriz[i,j]:=0;
            end;
            end
        else
        begin

        end;
        end;
      end;
     writeln ('Deseja: (a,b,c) ver a matriz de adjacencias, calcular a menor distancia entre dois vertices ou calcular o diametro do grafo, respectivamente');
     readln (resp2);
     case resp2 of
       'a':
       begin
         for i:=1 to n do
         begin
           for j:=1 to n do
           begin
             write (matriz[i,j],' ');
           end;
           writeln;
         end;
      end;
      'b':
      begin
        d:=0;
        repeat
          d:=d+1;
          writeln('Seu primeiro vertice e ',nome[d],'? (s,n)');
          readln (resp3);
        until resp3='s';
        e:=0;
        repeat
          e:=e+1;
          writeln ('Seu segundo vertice e ',nome[e],'? (s,n)');
          readln (resp3);
        until resp3='s';
        if matriz[d,e]=0 then
         begin
           if d<>e then
          begin
             for i:=1 to n do
             begin
               for j:=1 to n do
               begin
                 matrizaux[i,j]:=matriz[i,j]
               end;
             end;
             f:=1;
             repeat
               f:=f+1;
               matriz2[i,j]:=0;
                 For i:= 1 to n do
                 begin
                   For j:=1 to n do
                   begin
                     For k:= 1 to n do
                     begin
                       matriz2[i,j]:= matriz2[i,j] + matrizaux[i,k] * matriz[k,j];
                     end;
                   end;
                 end;
                 for i:= 1 to n do
                 begin
                   for j:=1 to n do
                   begin
                     matrizaux[i,j]:=matriz2[i,j]
                   end;
                 end;
            until matrizaux[d,e]>0;
            writeln('A menor distancia (em saltos) do par de vertices escolhido e: ',f);
           end
           else
           begin
             f:=0;
            writeln('A menor distancia (em saltos) do par de vertices escolhido e: ',f);
           end;
         end
        else
        begin
          f:=1;
          writeln('A menor distancia (em saltos) do par de vertices escolhido e: ',f);
        end;

      end;
      'c':
      begin
             for i:=1 to n do
             begin
               for j:=1 to n do
               begin
                 matrizaux[i,j]:=matriz[i,j];
                 if matriz [i,j]=0 then
                   g:=0
                 else
                 begin

                 end;
               end;
             end;
             for i:= 1 to n do
                   begin
                     for j:=1 to n do
                     begin
                         matrizaux2[i,j]:=matriz[i,j];
                         if matrizaux2[i,j]=0 then
                         begin
                           g:=0;
                         end
                         else
                         begin
                         end;
                     end;
                   end;
             f:=1;
             if g=0 then
             begin
               repeat
               g:=1;
                 f:=f+1;
                 matriz2[i,j]:=0;
                   For i:= 1 to n do
                   begin
                     For j:=1 to n do
                     begin
                       For k:= 1 to n do
                       begin
                         matriz2[i,j]:= matriz2[i,j] + matrizaux[i,k] * matriz[k,j];
                       end;
                     end;
                   end;
                   for i:= 1 to n do
                   begin
                     for j:=1 to n do
                     begin
                       matrizaux[i,j]:=matriz2[i,j]
                     end;
                   end;
                   for i:= 1 to n do
                   begin
                     for j:=1 to n do
                     begin
                       if matriz2[i,j]>=matrizaux2[i,j] then
                       begin
                         matrizaux2[i,j]:=matriz2[i,j];
                         if matrizaux2[i,j]=0 then
                         begin
                           g:=0;
                         end
                         else
                         begin
                         end;
                       end
                   else
                   begin
                   end;
                     end;
                   end;
              until g=1;
            end
            else
            begin

            end;
           writeln ('O diametro do grafo e: ',f);
      end;
    end;
   end
   else
   begin
     writeln ('Erro. O maximo de rotulos e 10 e o minimo e 2');
   end;
  end;
End.