Într-un graf neorientat, numim antilanț un șir de noduri S[1] S[2] ... S[k] cu proprietatea că oricare două noduri consecutive S[i] S[i+1], 1≤i<n, nu sunt adiacente. Un antilanț se numește elementar dacă nodurile din el nu se repetă.

Cerinţa

Se dă un graf neorientat cu n vârfuri și m muchii, un vârf x și un număr L. Să se determine toate antilanțurile elementare formate care încep cu nodul x și conțin cel puțin L noduri.

Date de intrare

Fişierul de intrare antilantxl.in conţine pe prima linie numerele n m x L. 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.

Date de ieşire

Fişierul de ieşire antilantxl.out va conține, în ordine lexicografică, toate antilanțurile lanțurile elementare care îndeplinesc condițiile cerute, fiecare antilanț fiind afișat pe câte o linie a fișierului, vârfurile dintr-un antilanț fiind separate prin exact un spațiu.

Dacă graful nu conține niciun antilanț care îndeplinește condițiile cerute, fișierul va conține doar mesajul NU EXISTA.

Restricţii şi precizări

• 1 ≤ n ≤ 20
• 1 ≤ x ≤ n
• 1 ≤ i, j ≤ n

Exemplu:

antilantxl.in

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

antilantxl.out

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