北极有 $$$n$$$ 驯鹿,它们都在争夺 CodeNorses(热门驯鹿竞技游戏网站)首页“顶级驯鹿”排行榜的最高位置。有趣的是,“顶级驯鹿”的称号只是一个点赞数的衡量标准,与他们在驯鹿比赛中的技术水平无关,但他们仍然非常重视它。
目前,第 $$$i$$$ 驯鹿的得分为 $$$a_i$$$。您想通过一些操作来影响排行榜。在一次行动中,您可以选择一头驯鹿,并以 $$$1$$$ 单位增加或减少他的分数。允许负分。
您对结果分数有 $$$m$$$ 要求。每个要求由有序对 $$$(u, v)$$$ 给出,意味着经过所有操作后,驯鹿 $$$u$$$ 的得分必须小于或等于驯鹿 $$$v$$$ 的得分。
您的任务是执行最少数量的操作,以便满足所有要求。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2\le n\le 1000$$$; $$$1\le m\le 1000$$$)——分别是驯鹿的数量和需求。
第二行包含$$$n$$$整数$$$a_1,\ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$),其中$$$a_i$$$是驯鹿$$$i$$$的当前分数。
接下来的 $$$m$$$ 行描述了要求。
这些行中的第 $$$i$$$ 包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1\le u_i, v_i\le n$$$; $$$u_i\ne v_i$$$) — 第 $$$i$$$ 要求的两只驯鹿。
输出
打印 $$$n$$$ 整数 $$$b_1,\ldots, b_n$$$ ($$$-10^{15}\le b_i\le 10^{15}$$$),其中 $$$b_i$$$ 是第 $$$i$$$ 个驯鹿在所有操作后的得分。
如果有多个解达到最少运算次数,则可以输出任何一个。
我们可以证明,对于所有$$$i$$$,总是存在一个最优解,使得$$$|b_i|\le 10^{15}$$$。
示例
输入 #1
7 6 3 1 4 9 2 5 6 1 2 2 3 3 4 4 5 5 6 6 7
输出 #1
1 1 4 4 4 5 6
输入 #2
4 6 6 5 8 2 3 1 4 1 3 2 1 2 2 3 3 1
输出 #2
6 6 6 2
输入 #3
10 18 214 204 195 182 180 176 176 172 169 167 1 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 6 1 6 2 6 3 6 4 6 5 6 7 6 8 6 9 6 10
输出 #3
204 204 195 182 180 167 176 172 169 167