长途巡游

【题目描述】

巡游车准备在城中的 $n$ 个站点之间行驶．站点编号为 $1,2,\ldots,n$，其中第 $i$ 个站点的通行等级为 $a_i$．站点之间有 $m$ 条单向道路，每条道路可以从一个站点直接驶向另一个站点．

巡游车可以任选一个站点出发，沿单向道路行驶，并在任意站点结束．它需要恰好访问 $k$ 次站点，出发时所在的站点也算一次．同一个站点和同一条道路都可以重复经过，每次到达站点都会计入访问次数．

一条巡游路线所需的通行等级，等于这条路线上所有被访问站点的通行等级的最大值．

请你求出满足要求的巡游路线所需的最低通行等级．如果不存在这样的路线，输出 -1．

【输入描述】

第一行包含三个整数 $n,m,k$，分别表示站点数、单向道路数和要求的访问次数．

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各站点的通行等级．

接下来 $m$ 行，每行包含两个整数 $u,v$，表示一条从站点 $u$ 驶向站点 $v$ 的单向道路．

保证没有从某个站点通向自身的道路，也没有两条起点和终点均相同的道路．从 $u$ 到 $v$ 和从 $v$ 到 $u$ 的道路可以同时存在．

【输出描述】

输出一个整数，表示所需的最低通行等级．如果不存在满足访问次数要求的路线，输出 -1．

【样例 1】

【样例 1 输入】

5 5 4
8 2 4 3 7
1 2
2 3
3 4
4 5
2 5

【样例 1 输出】

7

【样例 1 解释】

选择路线 $2\to3\to4\to5$，一共访问 $4$ 次站点，所需通行等级为 $\max(2,4,3,7)=7$．

如果通行等级小于 $7$，就只能访问站点 $2,3,4$，而这些站点之间最多只能连续访问 $3$ 次，不能满足要求．出发站点可以自行选择，不必是站点 $1$．

【样例 2】

【样例 2 输入】

4 3 8
1 5 3 9
2 3
3 2
1 4

【样例 2 输出】

5

【样例 2 解释】

可以依次访问 $2,3,2,3,2,3,2,3$，恰好访问 $8$ 次站点，所需通行等级为 $5$．不要求访问不同的站点，也不要求结束时回到出发站点．

【样例 3】

【样例 3 输入】

3 2 4
2 1 3
1 2
2 3

【样例 3 输出】

-1

【样例 3 解释】

即使不限制通行等级，也最多只能连续访问 $3$ 次站点．

【下发样例】

见选手目录中的 Data/sample4.in 至 Data/sample10.in，对应答案文件为同名的 .ans 文件．

点击下载选手目录

【数据规模与约定】

对于所有测试数据，保证：

• $1\le n\le2\times10^5$，$0\le m\le2\times10^5$．
• $1\le k\le10^{18}$．
• $1\le a_i\le10^9$．
• $1\le u,v\le n$，$u\ne v$．

每个子任务中的所有测试点均通过，才能获得该子任务的分数．各子任务相互独立．