== 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.

Georgel, 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 numarul 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. Georgel 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$ reprezentand numarul de baruri, numarul strazilor ce leaga baruri intre ele, respectiv coeficientul de siguranta $K$. Urmatoarea linie contine $N$ valori, $A[~i~]$ reprezentand indicele alcoolic pentru 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 drumul optim intre barul $1$ si $N$.
Pe urmatoarea linie se va afisa un drum de la barul $1$ la barul $N$.

h2. Restricţii

* $ N $le; 10 ^ 5 $
* $ M $le; 7 * 10 ^ 5 $
* $ K $le; 10 ^ 12 $
* $ 1 $le; A[i] $le; 10 ^ 12 $
* $ 1 $le; x, y $le; N $

* $1$ ≤ $N$ ≤ $10^5^$
* $1$ ≤ $M$ ≤ $7 * 10^5^$
* $2$ ≤ $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") ==