Rezolvare PBinfo #4074

Se consideră un graf neorientat conex cu n noduri, numerotate de la 1 la n, şi m muchii. Definim distanţa minimă dintre două noduri x şi y ca fiind numărul minim de muchii al unui lanţ elementar care uneşte x cu y.

Cerinţa

Se dă o pereche de noduri p q. Determinați nodurile r cu proprietatea că distanța minimă dintre p și r este egală cu distanța minimă dintre r și q.

Date de intrare

Fişierul de intrare distante.in conţine pe prima linie numere n m p q. Fiecare dintre următoarele m linii va conţine câte două numere x şi y, separate printr-un spaţiu, cu semnificaţia: există o muchie între nodul x şi nodul y.

Date de ieşire

Fişierul de ieşire distante.out va conține pe prime linie, separate prin câte un spațiu, modurile cerute în ordine crescătoare.

Restricţii şi precizări

• n ≤ 1000

Exemplu:

distante.in

7 8 2 4
1 2
2 3
2 6
3 4
3 6
3 7
4 5
4 6

distante.out

3 6 7