题目描述

一天，探险家EZ来到一个地下迷宫，地下迷宫有着无穷无尽的宝藏。

这个迷宫可以描述为由一张n个点，m条有向边构成的图（可能存在重边和自环）。对于每个点都有一个价值为vali的宝藏。

EZ希望你求出从每个点出发，作为起点，所能得到的宝藏最大价值是多少。

输入格式

第一行包括两个整数n，m。

第二行包括n个val，表示每个点宝藏的价值。

接下来m行，每行两个数u，v，表示u到v有一条有向边(u,v)。

输出格式

一行，n个数ansi，表示从i号点作为起点，所能得到的最大价值和是多少。

样例数据

输入样例1

4 3
1 2 3 4
1 2
2 4
4 3

输出样例1

4 4 3 4

样例说明

1号点可以到达1.2.4号点 ans1=4.

2号点可以到达2.4号点 ans2=4.

3号点可以到达3号点 ans3=4.

4号点可以到达4号点 ans4=4.

数据规模与约定

30%满足n,m<=1000.

另外30%满足m=n-1，n个点构成树形图.

100%满足n，m<=$10^5$,,0<=vali<=$10^9$.

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$