3681. 中位数

单点时限: 10.0 sec

内存限制: 256 MB

“你的地图是一张白纸,所以即使想决定目的地,也不知道路在哪里。”

QQ 小方最近在自学图论。他突然想出了一个有趣的问题:

一张由 个点, 条边构成的有向无环图。每个点有点权 。QQ 小方想知道所有起点为 ,终点为 的路径中最大的中位数是多少。

一条路径的中位数指的是:一条路径有 个点,将这 个点的权值从小到大排序后,排在位置 上的权值。

输入格式

第 1 行输入两个正整数 (),表示结点数量和边的数量。

第 2 行输入 个由空格隔开的整数 (),表示点权。

接下来 行,每行输入两个整数 (),表示有一条 指向 的单向边,保证给出的图是联通的,可能存在重边。

输出格式

输出一行包含一个整数,表示最大的中位数。如果不存在任何一条起点为 ,终点为 的路径,则输出

样例

Input
5 5
1 2 3 4 5
1 2
2 3
3 5
2 4
4 5
Output
4

64 人解决,104 人已尝试。

87 份提交通过,共有 547 份提交。

7.3 EMB 奖励。

创建: 7 月,3 周前.

修改: 7 月,3 周前.

最后提交: 2 月,3 周前.

来源: EOJ Monthly 2019.2

题目标签