题目描述

给定一张有向图，每个点有点权。试找到一条路径，使得该路径上的点权最大值减去点权最小值最大，问这个差最大是多少。

输入格式

一行两个整数$N,M$，代表点的数量和边的数量。

接下来一行$N$个整数代表每个点的点权。

接下来$M$行每行两个整数代表一条有向边。

输出格式

一行一个整数代表答案。

输入输出样例

样例输入

3 3
1 2 3
1 2
1 3
2 3

样例输出 #1

2

数据范围与约定

对于$20\%$的数据，$? \leq 50$。

对于$40\%$的数据，$? \leq 100$。

对于$60\%$的数据，$? \leq 1000$。

对于另外$20\%$的数据，图中没有环。

对于$100\%$的数据,$1<=?<=10^5$, $1<=?<=5 * 10^5$，点权不超过$10^6$。