← 返回题目列表

Codeforces · 1043/E

E. 努力训练,轻松获胜

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

Zibi 是一名竞技编程教练。有 $$$n$$$ 竞争对手希望做好充分准备。训练比赛很不寻常——一个团队中有两个人,两个问题,每个参赛者都会编写其中一个问题。当然,一个团队中的人员会编写不同的问题。

评分规则也不典型。第一个问题始终是实现问题:您必须非常快地实现一些众所周知的算法,并且对您的打字时间进行评级。第二个是一项可怕的几何任务,你只需要在合理的时间内接受它即可。在这里,代码的长度和难度很重要。之后,子笔会对每个解给予一些罚分(可能是负数),而队伍的最终得分就是它们的总和(得分越少越好)。

我们知道,第 $$$i$$$ 个参赛者在编写第一个任务时将始终获得 $$$x_i$$$ 分数,而在编写第二个任务时将始终获得 $$$y_i$$$ 分数。我们可以假设,所有参赛者都知道彼此的技能,并且在比赛期间以最小化最终得分的方式分配问题。请记住,每个人在竞赛中只编写一个问题。

Zibi 希望所有参赛者互相写一篇比赛。不过,也有$$$m$$$的人真的不喜欢合作,他们肯定不会一起写比赛。尽管如此,教练还是会对所有可能的配对进行训练,这样配对的人就不会互相讨厌。教练对每个参与者感兴趣,他或她在他所训练的所有球队中的得分总和是多少?

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 300\,000$$$, $$$0 \le m \le 300\,000$$$) – 参与者的数量和不会一起写比赛的人数。

接下来的 $$$n$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) - 第 $$$i$$$ 选手在第一个问题和第二个问题上获得的分数。保证不存在两个人的 $$$x_i$$$ 和 $$$y_i$$$ 相同。

接下来的 $$$m$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) - 不想在一个团队中撰写竞赛的人员的索引。每个无序索引对最多出现一次。

输出

输出 $$$n$$$ 整数 - 所有参与者的分数总和,按照输入中出现的顺序排列。

示例

输入 #1

3 2
1 2
2 3
1 3
1 2
2 3

输出 #1

3 0 3

输入 #2

3 3
1 2
2 3
1 3
1 2
2 3
1 3

输出 #2

0 0 0

输入 #3

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

输出 #3

4 14 4 16 10

注意

在第一个示例中,只有一个团队由 $$$1$$$ 和 $$$3$$$ 组成。他们的最佳策略是将第一个任务分配给第 $$$3$$$-rd 个人,将第二个任务分配给第 $$$1$$$-st 个人,这将导致得分等于 $$$1 + 2 = 3$$$。

在第二个示例中,没有人喜欢任何人,因此不会有任何培训。看来这样子比就不能当教练了……