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

Se considera un graf orientat cu $N$ noduri. Fiecare muchie a grafului are costul egal cu $1$. Se dau, de asemenea, si doua noduri $X$ si $Y$.

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

h2. Cerinta

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

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

h2. Date de intrare

Fisierul de intrare $bfs.in$ contine pe prima linie $N$ $X$ $Y$, cu semnificatia din enunt. Urmatoarele $N$ linii contin cate $N$ numere, reprezentand matricea de adiacenta a grafului. Cu alte cuvinte, al $j$-lea element de pe linia $i+1$ este egal cu $1$, daca exista muchie orientata de la $i$ spre $j$, respectiv $0$ in caz contrar.

Fisierul de intrare $bfs.in$ contine pe prima linie $N$ $X$ $Y$, cu semnificatia din enunt. Urmatoarele $N$ linii contin cate $N$ numere, reprezentand matricea de adiacenta a grafului. Cu alte cuvinte, al $j$-lea element de pe linia $i+1$ este egal cu $1$, daca exista arc orientat de la varful $i$ spre varful $j$, respectiv $0$ in caz contrar.

h2. Date de iesire

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

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.

h2. Restrictii
* $2 ≤ n ≤ 100 .$

* Prin drum de la nodul $A$ la nodul $B$, se intelege o insiruire $P$ de $K$ noduri, cu proprietatile:

* 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 muchie de la $P{~i~}$ la $P{~i+1~}$, pentru orice $i$ =1, $K$ - $1$.

** 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$.
* Distanta de la un varf la el insusi este egala cu $0$.

* Daca intre $X$ si $Y$ nu exista niciun lant, se va afisa $0$.

* Daca intre $X$ si $Y$ nu exista niciun drum, se va afisa $0$.

* Daca exista mai multe solutii, se poate afisa oricare.
h2. Exemplu