CF1043E Train Hard, Win Easy

Zibi 是一名竞赛编程教练。有 $n$ 名选手希望得到良好的训练。这些训练赛非常特别——每支队伍由两人组成，有两道题目，每位选手恰好负责一道题目。当然，同一队的两人要做不同的题目。 评分规则也很特殊。第一题总是实现题：你需要非常快地实现某个众所周知的算法，打字速度会被计分。第二题是一道非常难的几何题，你只需要在合理时间内通过即可，这里代码的长度和难度会影响得分。之后，Zibi 会为每份解答给出一些罚分（可能为负数），队伍的最终得分是两人得分之和（得分越低越好）。 我们知道，第 $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$ 位选手组成。最优策略是让第 $3$ 位选手做第一题，第 $1$ 位选手做第二题，这样得分为 $1 + 2 = 3$。 在第二个样例中，没有人喜欢别人，因此不会有任何训练。看来 Zibi 这次当不了教练了…… 由 ChatGPT 4.1 翻译