== include(page="template/taskheader" task_id="graf") ==
==Include(page="template/taskheader" task_id="graf")==
Poveste ...
Se stie ca intr-un graf neorientat conex, intre oricare doua varfuri exista cel putin un lant iar lungimea unui lant este egala cu numarul muchiilor care-l compun. Definim notiunea lant optim intre doua varfuri $X$ si $Y$ ca fiind un lant de lungime minima care are ca extremitati varfurile $X$ si $Y$. Este evident ca intre oricare doua varfuri ale unui graf conex vom avea unul sau mai multe lanturi optime, depinzand de configuratia grafului.
h2. Cerinta
...
Fiind dat un graf neorientat conex cu $N$ varfuri etichetate cu numerele de ordine $1,2,...,N$ si doua varfuri ale sale notate $X$ si $Y$ $(1 ≤ X,Y ≤ N, X!=Y)$, se cere sa scrieti un program care determina varfurile care apartin tuturor lanturilor optime dintre $X$ si $Y$.
h2. Restrictii
h2. Date de Intrare
Fisierul $graf.in$ contine
* pe prima linie patru numere naturale reprezentand: $N$ (numarul de varfuri ale grafului), $M$ (numarul de muchii), $X$ si $Y$ (cu semnificatia din enunt).
* pe urmatoarele $M$ linii cate doua numere naturale nenule $A{~i~},B{~i~}$ ({$1 ≤ A{~i~},B{~i~} ≤ N, A{~i~} != B{~i~}$}, pentru $1 ≤ i ≤ M$) fiecare dintre aceste perechi de numere reprezentand cate o muchie din graf.
...
h2. Date de Iesire
h2. Date de intrare
Fisierul $graf.out$ va contine
* pe prima linie, numarul de varfuri comune tuturor lanturilor optime dintre $X$ si $Y$;
* pe a doua linie, numerele corespunzatoare etichetelor acestor varfuri, dispuse in ordine crescatoare; intre doua numere consecutive de pe aceasta linie se va afla cate un spatiu.
...
h2. Restrictii
h2. Date de iesire
* $2 ≤ N ≤ 7500; 1 ≤ M ≤ 14000$
* pentru $50%$ din teste $N ≤ 200$
...
h2. Exemple
h2. Exemplu
table(example). |_. graf.in |_. graf.out |
| 6 7 1 4
1 2
1 3
1 6
2 5
3 5
5 6
5 4 | 3
1 4 5 |
| 3 2 1 3
1 2
3 1 | 2
1 3 |
| graf.in | graf.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="graf") ==
==Include(page="template/taskfooter" task_id="graf")==
