Rezolvare PBinfo #3422

Cerința

Se dă un graf orientat cu n vârfuri și m arce prin lista arcelor și un număr natural k. Afișați vârfurile din graf care se află la distanță k față de vârful 1. Distanța dintre două vârfuri x și y este egală cu k dacă cel mai scurt drum care are ca extremitate inițială pe x și ca extremitate finală pe y are lungimea k sau cel mai scurt drum care are ca extremitate inițială pe y și ca extremitate finală pe x are lungimea k.

Date de intrare

Programul citește de la tastatură numărul n de noduri și numărul m de arce și numărul k, 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 crescătoare și separate prin câte un spațiu vârfurile din graf care se află la distanță k față de vârful 1. Dacă nu există nici un vârf care să îndeplinească condiția, atunci se va afișa Nu exista.

Restricții și precizări

• 1 ≤ k ≤ n ≤ 100

Exemplu:

Intrare

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

Ieșire

2 5 6

Explicație

Drumurile de lungime minimă care au lungimea egală cu 2 și o extremitate în vârful 1 sunt:
[1, 4, 2]
[1, 8, 2]
[1, 3, 5]
[1, 4, 6]
[5, 7, 1]