I. Минимакс на пути

В каждой вершине ориентированного графа записано число. Фишку кладут в любую вершину и делают ровно $k-1$ ход по рёбрам; каждый раз, когда фишка оказывается в вершине (включая начальную), выписывается её число. Сделайте так, чтобы наибольшее выписанное число было как можно меньше.

Число ходов доходит до $10^{18}$, так что перебирать ходы нельзя.

В первой строке - числа $n$, $m$, $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 2 \cdot 10^5$, $1 \le k \le 10^{18}$).

Во второй строке - $n$ чисел $a_i$ ($1 \le a_i \le 10^9$).

В следующих $m$ строках - рёбра $u \to v$ ($u \ne v$). Кратных рёбер нет.

Выведите наименьшее возможное значение наибольшего выписанного числа или -1, если сделать $k-1$ ход невозможно.