题目描述

给定$n$个点$m$条边的无向图，每个点有自己的权值$a_i$，对于每一个点$i$，其能遍历到的最大权值记为$F(i)$，对于$1$到$n$，请输出每个点对应的$F(i)$。

显然，本题中图不一定连通。

输入格式

第一行输入两个整数$n,m$。 第二行输入$n$个整数$a_i$。 接下来$m$行，每行输入两个整数$u_i,v_i$，表示一条边。

输出格式

输出$n$行，第$i$行输出一个整数$F(i)$。

样例输入 #1

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

样例输出 #1

5
3
3
5
5

说明/提示

对于40%的数据，有$1\leq n\leq 1000,1\leq m\leq 10000$。 对于100%的数据，有$1\leq n\leq 10^5,1\leq m\leq 5\times 10^5,1\leq a_i\leq 10^9$。