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≠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 se află câte două numere naturale nenule Ai, Bi (1 ≤Ai, Bi ≤ N, Ai ≠ Bi, 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 se vor scrie 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 ≤ 7500
1 ≤ M ≤ 14000
Pentru 50% din teste N ≤ 200