Cerinţa

Se dă un graf neorientat cu n vârfuri și două numere naturale p și q. Să se determine toate lanțurile elementare formate din cel puțin p muchii și cel mult q muchii, adică au lungimea în intervalul [p,q].

Date de intrare

Fişierul de intrare lantpq.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ă numerele p și q.

Date de ieşire

Fişierul de ieşire lantpq.out va conține, în ordine lexicografică, toate lanțurile elementare care îndeplinesc condițiile cerute, 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ț care îndeplinește condițiile cerute, atunci se va afișa NU EXISTA.

Restricţii şi precizări

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

Exemplu:

lantpq.in

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

lantpq.out

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

Explicație:

S-au afișat în ordine lexicografică lanțurile formate din cel puțin două și cel mult 3 muchii.