Rezolvare PBinfo #3451

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 în ordine lexicografică drumurile simple din graf care au lungimea egală cu k. Lungimea unui drum este egală cu numărul de arce pe care le conține.

Date de intrare

Programul citește de la tastatură numărul n de noduri și numărul m de arce și un număr k. Apoi se citește 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 afișează pe rânduri separate în ordine lexicografică drumurile simple din graf care au lungimea egală cu k. Nodurile din care sunt formate drumurile sunt se afișează separate prin cîte un spațiu. Dacă nu există drumuri simple de lungime k, atunci programul va afișa Nu exista.

Restricții și precizări

• 1 ≤ n ≤ 20
• 1 ≤ k ≤ 10

Exemplu:

Intrare

7 10 6
1 2
1 3
1 4
1 5
2 5
5 1
3 4
4 3
4 6
4 7

Ieșire

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