Rezolvare PBinfo #541

Cerinţa

Se dă lista muchiilor unui graf neorientat și trei vârfuri p q r . Să se determine un lanț cu extremitățile p q care conține vârful r.

Date de intrare

Fişierul de intrare lant1.in conţine pe prima linie numerele n p q r, reprezentând numărul de vârfuri ale grafului și cele trei vârfuri date. Fiecare dintre următoarele 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 lant1.out va conţine pe prima linie numărul de vârfuri din lanțul determinat. A doua linie va conține vârfurile din acest lanț, separate prin exact un spațiu.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• în fișierul de intrare muchiile se pot repeta;
• orice lanț cu extremitățile p q care conține vârful r și are lungimea mai mică decât 2*n este acceptat; lanțul nu trebuie să fie elementar
• pentru toate datele de test există cel puțin un lanț care respectă cerința;

Exemplu:

lant1.in

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

lant1.out

5
5 1 3 2 7