path2

Path2

h2. Date de iesire

Pe prima linie a fisierului $path2.out$ veti afisa $T$, reprezentand durata minima (in ore) a unui traseu care trece prin orasul $I$ si se termina in orasul $J$. Pe a doua linie veti afisa numarul variantelor distincte de a ajunge in orasul $J$ in timpul $T$ (trecand prin orasul $I$). Pe urmatoarele linii veti afisa toate variantele (de lungime minima) de a ajunge in orasul $J$, trecand prin orasul $I$. Daca numarul acestor variante depaseste $100$, atunci afisati doar $100$ dintre ele (oricare $100$). O varianta va fi afisata ca o succesiune de orase prin care trece Gigi: orasul de start ($1$) , orasul urmator, .. , $I$ , .. , $J$, separate prin spatii. Intre oricare doua orase consecutive trebuie sa existe o legatura directa. Fiecare varianta va fi afisata pe o linie de una singura.

Pe prima linie a fisierului $path2.out$ veti afisa $T$, reprezentand durata minima (in ore) a unui traseu care trece prin orasul $I$ si se termina in orasul $J$. Pe a doua linie veti afisa numarul variantelor distincte de a ajunge in orasul $J$ in timpul $T$ (trecand prin orasul $I$). Pe urmatoarele linii veti afisa toate variantele (de lungime minima) de a ajunge in orasul $J$, trecand prin orasul $I$. Daca numarul acestor variante depaseste $100$, atunci afisati doar $100$ dintre ele (oricare $100$). O varianta va fi afisata ca o succesiune de orase prin care trece Gigi: orasul de start ({$1$}) , orasul urmator, .. , $I$ , .. , $J$, separate prin spatii. Intre oricare doua orase consecutive trebuie sa existe o legatura directa. Fiecare varianta va fi afisata pe o linie de una singura.

h2. Restrictii
* $3 ≤ N ≤ 100$
* $1 < I,J ≤ N$
* $I <> J$

* $3 ≤ N ≤ 100$

* $2 ≤ M ≤ N*(N-1)/2$
* Timpul necesar parcurgerii unei legaturi directe intre $2$ orase este $1$ ora. Asadar, o varianta de lungime minima de a ajunge din orasul $1$ in orasul $J$, trecand si prin orasul $I$ este reprezentata printr-o succesiune de $T+1$ orase (unde $T$ este timpul minim ce trebuie calculat)

* Numarul variantelor distincte de lungime minima va fi minim $1$ si  maxim $2 000 000 000$

* Numarul variantelor distincte de lungime minima va fi minim $1$ si maxim $2 000 000 000$

* Lui Gigi ii este permis sa treaca prin orasul $J$ inainte de a ajunge in orasul $I$, dar el nu poate incheia contractul in orasul $J$ decat dupa ce a trecut prin orasul $I$ (asta inseamna ca ultimul oras al traseului sau trebuie sa fie obligatoriu orasul $J$)
h2. Exemplu

4 6
5 7
6 7

|
6

|6

8
1 2 4 5 7 5 4
1 2 4 5 7 6 4

== include(page="template/taskfooter" task_id="path2") ==

2146