Rezolvare PBinfo #484

Cerinţa

Se dă lista muchiilor unui graf neorientat și două vârfuri p q . Să se determine cel mai scurt lanț cu extremitățile p q.

Date de intrare

Fişierul de intrare lantminim.in conţine pe prima linie numerele n p q, reprezentând numărul de vârfuri ale grafului și cele două 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 lantminim.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ț de lungime minimă cu extremitățile p q este acceptat;
• pentru toate datele de test există cel puțin un lanț de la p la q;

Exemplu

lantminim.in

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

lantminim.out

4
2 1 4 6