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