如同瞬变的烟火，一分钟她也能变幻数十种颜色。
烟花表演即将结束之时，她坐在高处，无聊地俯视着脚下熙熙攘攘的人群。
一个个念头游动又消失，狡黠的光在万花筒般的眼眸中流转。
「想好了，今天就这样玩！」
她蹦蹦跳跳，在人群中穿梭，金红的尾摆忽隐忽现。
「别跟丢啦，最美的烟花，才刚刚开始！」

假面愚者花火在玩欢愉的组合烟花。
欢愉的组合烟花可以视为一个简单有向图，即无自环和重边。第 i 个节点的权值为 a[i] 。
花火可以任选一个点作为起点，任意移动 k-1 次，每次沿着当前点的出边移动至边的另一个端点，共经过 k 个节点。求经过的点的权值的最大值最小可能是多少？
如果不存在能移动 k-1 次的方案，则输出 -1 。

第一行包含三个正整数 n,m,k (1≤n≤2·10^5, 0≤m≤2·10^5, 1≤k≤10^18) ，表示有向图的节点数、边数、移动步数。
第二行包含 n 个正整数 a[1],a[2],...,a[n] (1≤a[i]≤10^9) ，表示每个节点的权值。
接下来 m 行，每行包含两个整数 u,v (1≤u,v≤n, u≠v) ，表示存在一条有向边 u->v 。

保证图中没有重边和自环。

输出一个整数，表示答案。

样例1：
6 7 4
1 10 2 3 4 5
1 2
1 3
3 4
4 5
5 6
6 2
2 5

样例2：
6 7 100
1 10 2 3 4 5
1 2
1 3
3 4
4 5
5 6
6 2
2 5

样例3：
2 1 5
1 1
1 2

样例4：
1 0 1
1000000000

样例1：
4

样例2：
10

样例3：
-1

样例4：
1000000000

样例1、2的图如下所示：

样例1中，可以沿着路径 1->3->4->5 移动，经过的最大点权是 4 。
样例2中，可以沿着环形路径 2->5->6->2->... 移动，经过的最大点权是 10 。