单点时限: 10.0 sec
内存限制: 256 MB
“你的地图是一张白纸，所以即使想决定目的地，也不知道路在哪里。”
QQ 小方最近在自学图论。他突然想出了一个有趣的问题：
一张由 n 个点，m 条边构成的有向无环图。每个点有点权 Ai。QQ 小方想知道所有起点为 1 ，终点为 n 的路径中最大的中位数是多少。
一条路径的中位数指的是：一条路径有 n 个点，将这 n 个点的权值从小到大排序后，排在位置 ⌊n2⌋+1 上的权值。
第 1 行输入两个正整数 n,m (1≤n≤106,1≤m≤106)，表示结点数量和边的数量。
第 2 行输入 n 个由空格隔开的整数 Ai (0≤Ai≤109)，表示点权。
接下来 m 行，每行输入两个整数 x,y (1≤x,y≤n)，表示有一条 x 指向 y 的单向边，保证给出的图是联通的，可能存在重边。
输出一行包含一个整数，表示最大的中位数。如果不存在任何一条起点为 1 ，终点为 n 的路径，则输出 −1 。
5 5 1 2 3 4 5 1 2 2 3 3 5 2 4 4 5
4