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

<Insert name>, mare iubitor de alcool si olimpic la informatica tocmai a descoperit conceptul de pub crawling (https://en.wikipedia.org/wiki/Pub_crawl). Foarte entuziasmat, s-a informat si a aflat de N puburi care sunt conectate intre ele prin strazi uni-directionale. El s-a hotarat sa porneasca intr-un pub crawl din barul identificat cu nr 1 care este langa scoala sa, pana la barul N, situat langa Strada Cramei, unde protagonistul nostru locuieste. In urma unei atente analize el a aflat un indice alcoolic pentru fiecare pub. Stiind un coeficient de siguranta K, el vrea sa-si planifice traseul astfel incat produsul indicilor alcoolici de pe drum sa contina K la o putere cat mai mica. Daca reuseste sa determine un astfel de drum optim eroul nostru va ajunge acasa cu success. Se garanteaza ca isprava este posibila. <Insert Name> nu poate dezlega acest mister singur, motiv pentru care va cere ajutorul.

<Insert name>, mare iubitor de alcool si olimpic la informatica tocmai a descoperit conceptul de pub crawling (https://en.wikipedia.org/wiki/Pub_crawl). Foarte entuziasmat, s-a informat si a aflat de $N$ puburi care sunt conectate intre ele prin strazi uni-directionale. El s-a hotarat sa porneasca intr-un pub crawl din barul identificat cu nr 1 care este langa scoala sa, pana la barul $N$, situat langa Strada Cramei, unde protagonistul nostru locuieste. In urma unei atente analize el a aflat un indice alcoolic pentru fiecare pub. Stiind un coeficient de siguranta $K$, el vrea sa-si planifice traseul astfel incat produsul indicilor alcoolici de pe drum sa contina $K$ la o putere cat mai mica. Daca reuseste sa determine un astfel de drum optim eroul nostru va ajunge acasa cu success. Se garanteaza ca isprava este posibila. <Insert Name> nu poate dezlega acest mister singur, motiv pentru care va cere ajutorul.

h2. Date de intrare

Fişierul de intrare $pesaptecarari.in$ ..
 
Prima linie contine 3 numere N, M, K corespunzand numarului de baruri, numarului strazilor ce leaga baruri intre ele, respectic coeficientul de siguranta K.
Urmatoarea linie contine N valori, $A[~i~]$ corespunzand indicelui alcoolic pt fiecare pub din cele N.
Urmatoarele M linii contin cate 2 numere: x y aratand ca exista un drum cu sens unic de la x la y.

Fişierul de intrare $pesaptecarari.in$ va contine pe prima linie. $3$ numere $N$, $M$, $K$ corespunzand numarului de baruri, numarului strazilor ce leaga baruri intre ele, respectic coeficientul de siguranta $K$. Urmatoarea linie contine $N$ valori, $A[~i~]$ corespunzand indicelui alcoolic pt fiecare pub din cele $N$. Urmatoarele $M$ linii contin cate $2$ numere: $x$ $y$ aratand ca exista un drum cu sens unic de la $x$ la $y$.

h2. Date de ieşire

În fişierul de ieşire $pesaptecarari.out$ ...
 
Pe prima linie se va afisa puterea minima la care apare K in produsul indicilor alcoolici pt un puburile de pe un drum optim.
Pe urmatoarea linie se va afisa un drum de la barul 1 la barul N.

Fişierul de ieşire $pesaptecarari.out$ va contine pe prima linie puterea minima la care apare $K$ in produsul indicilor alcoolici pentru un puburile de pe un drum optim.
Pe urmatoarea linie se va afisa un drum de la barul $1$ la barul $N$.

h2. Restricţii

* N <= $10^5^$
* M <= $7 * 10^5^$
* K <= $10^12^$
* 1 <= $A[~i~]$ <= $10^12^$
* 1 <= x, y <= N

* $1$ ≤ $N$ ≤ $10^5^$
* $1$ ≤ $M$ ≤ $7 * 10^5^$
* $1$ ≤ $K$ ≤ $10^12^$
* $0$ ≤ $A[~i~]$ ≤ $10^12^$
* $1$ ≤ $x$ ≤ $N$
* $1$ ≤ $y$ ≤ $N$

* In caz ca exista mai multe drumuri optime, se poate afisa oricare.
h2. Exemplu

  1 2 4 5
|

h3. Explicaţie
Exista doua drumuri intre 1 si 5:
1. Primul este 1 -> 2 -> 4 -> 5, cu produsul 3 * 2 * 2 * 2 = 24 => puterea maxima la care apare 4 este 1
2. Al doilea este 1 -> 3 -> 5, cu produsul 3 * 8 * 2 = 48 => puterea maxima la care apare 4 este 2

h2. Explicaţie
 
Exista doua drumuri intre $1$ si $5$:
1. Primul este $1$ -> $2$ -> $4$ -> $5$, cu produsul $3$ * $2$ * $2$ * $2$ = $24$ => puterea maxima la care apare $4$ este $1$
2. Al doilea este $1$ -> $3$ -> $5$, cu produsul $3$ * $8$ * $2$ = $48$ => puterea maxima la care apare $4$ este $2$

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