← 返回题目列表

Codeforces · 1615/H

H. 驯鹿游戏

中文机器翻译题面 查看原题

北极有 $$$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