#P17838. [ONTAK 2021]GRA

[ONTAK 2021]GRA

最大最小游戏

一个有向图的点 ii 上写着正整数 aia_i。棋子最初在点 11。Amelia 先手,两人轮流行动,每次可以沿一条出边移动棋子,也可以立即结束游戏。结束时棋子所在点的数值就是游戏结果。

Amelia 希望结果尽量大,Bazyli 希望结果尽量小。如果没有人提前结束,棋子移动恰好 1010010^{100} 次后自动结束,并以当时所在点的数值为结果。双方均采取最优策略,求最终结果。

输入格式

第一行 n,mn,m,第二行 nn 个数 aia_i。接下来 mm 行,每行 x,yx,y,表示有向边 x→yx\to y。允许重复边,没有自环。

输出格式

输出最优博弈结果。

数据范围

1≤n≤2500001\le n\le250000,1≤m≤5000001\le m\le500000,1≤ai≤1091\le a_i\le10^9,1≤x,y≤n1\le x,y\le n,x≠yx\ne y。

样例

4 4
1 10 4 5
1 2
2 3
2 4
3 1
4