== include(page="template/taskheader" task_id="bfs") ==

Se considera un graf orientat cu $N$ varfuri si $M$ arce. Fiecare arc al grafului are costul egal cu $1$. Se dau, de asemenea, si doua varfuri $X$ si $Y$.

Se considera un graf orientat cu $N$ varfuri si $M$ arce.

h2. Cerinta

Se cere determinarea celui mai scurt drum dintre varfurile $X$ si $Y$.

Fiind dat un nod $x$, sa se determine, pentru fiecare nod, numarul minim de arce ce trebuie parcurse pentru a ajunge din nodul $x$ la nodul respectiv.

h2. Date de intrare

Fisierul de intrare $bfs.in$ contine pe prima linie $N$ $M$ $X$ $Y$, cu semnificatia din enunt. Urmatoarele $M$ linii contin cate doua numere $x $y$, cu semnificatia ca exista arc orientat de la $x$ la $y$.

Fisierul de intrare $bfs.in$ contine pe prima linie 3 numere intregi $N$ $M$ $X$, cu semnificatia din enunt. Urmatoarele $M$ linii contin cate doua numere $x $y$, cu semnificatia ca exista arc orientat de la $x$ la $y$.

h2. Date de iesire

In fisierul de iesire $bfs.out$ va fi afisata pe prima linie lungimea celui mai scurt drum dintre varfurile $X$ si $Y$. Linia a doua va contine o insiruire de varfuri, reprezentand unul din drumurile de lungime minima dintre cele doua varfuri date, separate prin cate un spatiu.

In fisierul de iesire $bfs.out$ se vor afla $N$ numere separate prin spatiu cu semnificatia ca al $i$-lea numar reprezinta numarul minim de arce ce trebuie parcurse de la nodul $x$ la nodul $i$.

h2. Restrictii

* $2 ≤ $N$ ≤ 1000 .$
* $1 ≤ $M$ ≤ $min$ ( $100.000$ , N * ( $N$ + $1$ )/ $2$ ).$
* $X$ diferit de $Y$.
* Prin drum de la varful $A$ la varful $B$, se intelege o insiruire $P$ de $K$ varfuri, cu proprietatile:
** $P{~1~}$ = $A$.
** $P{~K~}$ = $B$.
** Exista arc de la $P{~i~}$ la $P{~i+1~}$, pentru orice $i$ =1, $K$ - $1$.
** $P{~i~}$ diferit de $P{~j~}$ , pentru orice $i$ diferit de $j$.
* Daca intre $X$ si $Y$ nu exista niciun drum, se va afisa $0$.
* Daca exista mai multe solutii, se poate afisa oricare.

* $2 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 1 000 000$
* Daca nu se poate ajunge din nodul $x$ la nodul $i$, atunci numarul corespunzator numarului $i$ va fi $-1$.

h2. Exemplu