Rezolvare PBinfo #4633

Cerința

Se dă un graf orientat cu n vârfuri și m arce. Vârfurile x și y se numesc prietene dacă distanța minimă de la vârful x la vârful y este egală cu distanța minimă de la vârful y la vârful x. Distanța minimă de la vârful x la vârful y este egală cu lungimea celui mai scurt drum care are ca extremitate ințială vârful x și extremitate finală vârful y.

Date de intrare

Programul citește de la tastatură numărul n de noduri și numărul m de arce, iar apoi lista arcelor, formată din m perechi de forma i j, cu semnificația că există arc de la nodul i la nodul j.

Date de ieșire

Programul va afișa pe ecran în ordine lexicografică și separate prin câte un spațiu perechile de vârfuri prietene. În cadrul fiecărei perechi afișate cele două vârfuri se afișează înordine crescătoare. Dacă nu există nicio pereche care să îndeplinească condiția, atunci se va afișa Nu exista.

Restricții și precizări

• 1 ≤ n ≤ 100
• 1 ≤ m ≤ 200

Exemplu:

Intrare

6 12
1 2
1 3
1 6
2 4
2 5
2 6
3 4
4 5
5 6
6 1
5 2
5 1

Ieșire

1 4
1 6
2 3
2 5
3 5

Explicație

Vârfurile 1 și 4 sunt prietene deoarece drumurile cu distanță minime sunt (1,3,4) și (4,5,1).
Vârfurile 1 și 6 sunt prietene deoarece drumurile cu distanță minime sunt (1,6) și (6,1).
Vârfurile 2 și 3 sunt prietene deoarece drumurile cu distanță minime sunt (2,6,1,3) și (3,4,5,2).
Vârfurile 2 și 5 sunt prietene deoarece drumurile cu distanță minime sunt (2,5) și (5,2).
Vârfurile 3 și 5 sunt prietene deoarece drumurile cu distanță minime sunt (3,4,5) și (5,1,3).