Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri și un vârf q. Să se determine cel mai lung lanț elementar cu extremitatea finală în q.

Date de intrare

Fişierul de intrare lantmaxim1.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.

Următoarea linie conține numărul q.

Date de ieşire

Fişierul de ieşire lantmaxim1.out va conține cel mai lung lanț elementar cu extremitate finală q, vârfurile sale fiind separate prin exact un spațiu. Dacă sunt mai multe lanțuri de lungime maximă, se va afișa primul în ordine lexicografică.

Restricţii şi precizări

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

Exemplu:

lantmaxim1.in

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

lantmaxim1.out

2 1 3 4 5