MODULE Put;

  FROM IO IMPORT
    WrLn, WrStr, RdCard, WrCard, OK;

  FROM Storage IMPORT
    ALLOCATE;

  CONST
    MaxBrGrad = 50;

  TYPE
    Lista = POINTER TO Grad;
    Grad = RECORD
             Info: CARDINAL;
             Veza: Lista;
           END;
    Mreza = ARRAY  [1 .. MaxBrGrad] OF Lista;
    Posecen = ARRAY [1 .. MaxBrGrad] OF BOOLEAN;

  VAR
    m: Mreza;
    BrojGr: CARDINAL;
    GPoc, GKra: CARDINAL;

  PROCEDURE Ubaci(VAR L: Lista; G: CARDINAL);
    VAR
      Tek, Novi: Lista;
  BEGIN
    IF (L = NIL) OR (G < L^.Info) THEN
      NEW(Novi);
      Novi^.Info:= G;
      Novi^.Veza:= L;
      L:= Novi;
    ELSE
      Tek:= L;
      WHILE (Tek^.Veza # NIL) AND (Tek^.Veza^.Info < G) DO
        Tek:= Tek^.Veza;
      END;
      IF (Tek^.Veza = NIL) OR (Tek^.Veza^.Info > G) THEN
        NEW(Novi);
        Novi^.Info:= G;
        Novi^.Veza:= Tek^.Veza;
        Tek^.Veza:= Novi;
      END;
    END;
  END Ubaci;

  PROCEDURE Povezi(G1, G2: CARDINAL);
  BEGIN
    Ubaci(m[G1], G2);
    Ubaci(m[G2], G1);
  END Povezi;

  PROCEDURE Unos(VAR G1, G2: CARDINAL);
    VAR
      G: CARDINAL;
  BEGIN
    REPEAT
      WrStr('Unesite broj gradova (od 2 do ');
      WrCard(MaxBrGrad, 1);
      WrStr(') ---- ');
      BrojGr:= RdCard();
      WrLn;
    UNTIL OK AND (2 <= BrojGr) AND (BrojGr <= MaxBrGrad);
    FOR G:= 1 TO BrojGr DO
      m[G]:= NIL;
    END;
    REPEAT
      WrStr('Unesite dva grada koji su povezani linijom.');
      REPEAT
        WrLn;
        WrStr('Unesite red. br. prvog grada (ili 0 za kraj unosa linija) -- ');
        G1:= RdCard()
      UNTIL OK AND (G1 <= BrojGr);
      IF G1 > 0 THEN
        REPEAT
          WrStr('Unesite red. br. drugog grada ------------------------------ ');
          G2:= RdCard();
        UNTIL OK AND (1 <= G2) AND (G2 <= BrojGr) AND (G1 # G2);
        Povezi(G1, G2);
      END;
      WrLn;
    UNTIL G1 = 0;
    REPEAT
      WrLn;
      WrLn;
      WrStr('Unesite red. br. pocetnog grada -- ');
      G1:= RdCard();
    UNTIL OK AND (1 <= G1) AND (G1 <= BrojGr);
    REPEAT
      WrLn;
      WrStr('Unesite red. br ciljnog grada -- ');
      G2:= RdCard();
    UNTIL OK AND (1 <= G2) AND (G2 <= BrojGr) AND (G1 # G2);
  END Unos;

  PROCEDURE NadjiPut(Od, Do, brojGr : CARDINAL);
    VAR
     Pos: Posecen;
     Reseno: BOOLEAN;
     i: CARDINAL;
     Resenje: ARRAY [1 .. MaxBrGrad] OF CARDINAL;

    PROCEDURE Pokusaj(Od, Br: CARDINAL; VAR Reseno: BOOLEAN);
      VAR
        Pok: Lista;
    BEGIN
      Pos[Od]:= TRUE;
      Resenje[Br]:= Od;
      IF Od = Do THEN
        Reseno:= TRUE;
        WrLn;
        WrStr('Put koji treba precji je sledeci:');
        WrLn;
        FOR i:= 1 TO Br DO
          WrCard(Resenje[i], 4);
        END;
      ELSE
        Pok:= m[Od];
        WHILE (Pok # NIL) AND NOT Reseno DO
          WHILE (Pok # NIL) AND Pos[Pok^.Info]  DO
            Pok:= Pok^.Veza;
          END;
          IF Pok # NIL THEN
            Pokusaj(Pok^.Info, Br + 1, Reseno);
          END;
        END;
      END;
    END Pokusaj;

  BEGIN
    Reseno:= FALSE;
    FOR i:= 1 TO BrojGr DO
      Pos[i]:= FALSE;
    END;
    Pokusaj(Od, 1, Reseno);
  END NadjiPut;

BEGIN
  Unos(GPoc, GKra);
  NadjiPut(GPoc, GKra, BrojGr);
END Put.