Rezolvare PBinfo #4061

Cerinţa

Se dă un graf neorientat cu n vârfuri și un număr natural q. Să se determine toate lanțurile elementare formate din cel puțin o muchie, cu extremitatea finală în vârful q.

Date de intrare

Fişierul de intrare lantq.in conţine pe prima linie numerele n și m, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele m linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Pe ultima linie se află numărul q.

Date de ieşire

Fişierul de ieşire lantq.out va conține, în ordine lexicografică, toate lanțurile elementare cu extremitatea finală în vârful q, fiecare lanț fiind afișat pe câte o linie a fișierului, vârfurile dintr-un lanț fiind separate prin exact un spațiu. Dacă graful nu conține niciun lanț elementar format din cel puțin o muchie, cu extremitatea finală în vârful q, atunci se va afișa NU EXISTA.

Restricţii şi precizări

• 1 ≤ n ≤ 20
• 1 ≤ q ≤ n
• 1 ≤ i, j ≤ n
• muchiile se pot repeta în fișierul de intrare

Exemplu:

lantq.in

5 8
1 4 
1 3 
3 5 
4 5 
2 4 
1 2 
4 2 
3 4
5

lantq.out

1 2 4 3 5 
1 2 4 5 
1 3 4 5 
1 3 5 
1 4 3 5 
1 4 5 
2 1 3 4 5 
2 1 3 5 
2 1 4 3 5 
2 1 4 5 
2 4 1 3 5 
2 4 3 5 
2 4 5 
3 1 2 4 5 
3 1 4 5 
3 4 5 
3 5 
4 1 3 5 
4 2 1 3 5 
4 3 5 
4 5