graf

Se ştie că într-un graf neorientat conex, între oricare două vârfuri există cel puţin un lanţ iar lungimea unui lanţ este egală cu numărul muchiilor care-l compun. Definim noţiunea lanţ optim între două vârfuri $X$ şi $Y$ ca fiind un lanţ de lungime minimă care are ca extremităţi vârfurile $X$ şi $Y$. Este evident că între oricare două vârfuri ale unui graf conex vom avea unul sau mai multe lanţuri optime, depinzând de configuraţia grafului.

Cerinţă:

Fiind dat un graf neorientat conex cu $N$ vârfuri etichetate cu numerele de ordine $1, 2, ..., N$ şi două vârfuri ale sale notate $X$ şi $Y$ ($1 ≤ X, Y ≤ N, X \neq Y$), se cere să scrieţi un program care determină vârfurile care aparţin tuturor lanţurilor optime dintre $X$ şi $Y$.

Date de intrare:

Fişierul graf.in conţine

• pe prima linie patru numere naturale reprezentând: $N$ (numărul de vârfuri ale grafului), $M$ (numărul de muchii), $X$ şi $Y$ (cu semnificaţia din enunţ).
• pe următoarele $M$ linii câte două numere naturale nenule $A_i, B_i$ ($1 ≤ A_i, B_i ≤ N, A_i \neq B_i$ , pentru $1 ≤ i ≤ M$ ) fiecare dintre aceste perechi de numere reprezentând câte o muchie din graf.

Date de ieşire:

Fişierul graf.out va conţine

• pe prima linie, numărul de vârfuri comune tuturor lanţurilor optime dintre $X$ şi $Y$;
• pe a doua linie, numerele corespunzătoare etichetelor acestor vârfuri, dispuse în ordine crescătoare; între două numere consecutive de pe această linie se va afla câte un spaţiu.

Restricţii:

• $2 ≤ N ≤ 7\ 500$
• $1 ≤ M ≤ 14\ 000$
• pentru $50$ din teste $N ≤ 200$

Exemple

graf.in

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

graf.out

3
1 4 5

graf.in

3 2 1 3
1 2
3 1

graf.out

2
1 3