← 返回题目列表

Codeforces · 978/F

F. 导师

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

在 BerSoft $$$n$$$ 程序员工作中,程序员 $$$i$$$ 的特点是技能 $$$r_i$$$。

程序员 $$$a$$$ 可以成为程序员 $$$b$$$ 的导师,当且仅当程序员 $$$a$$$ 的技能严格高于程序员 $$$b$$$ $$$(r_a > r_b)$$$ 并且程序员 $$$a$$$ 和 $$$b$$$ 没有争吵时。

您将获得每个程序员的技能以及处于争吵状态的 $$$k$$$ 程序员对的列表(对无序)。对于每个程序员 $$$i$$$,找到程序员 $$$i$$$ 可以成为其导师的程序员数量。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ $$$(2 \le n \le 2 \cdot 10^5$$$, $$$0 \le k \le \min(2 \cdot 10^5, \frac{n \cdot (n - 1)}{2}))$$$ — 程序员总数和程序员对的数量争吵。

第二行包含整数序列 $$$r_1, r_2, \dots, r_n$$$ $$$(1 \le r_i \le 10^{9})$$$,其中 $$$r_i$$$ 等于第 $$$i$$$ 个程序员的技能。

以下 $$$k$$$ 行中的每一行都包含两个不同的整数 $$$x$$$, $$$y$$$ $$$(1 \le x, y \le n$$$, $$$x \ne y)$$$ — 一对正在争吵的程序员。这些对是无序的,这意味着如果 $$$x$$$ 与 $$$y$$$ 发生争吵,则 $$$y$$$ 与 $$$x$$$ 发生争吵。保证,对于每对 $$$(x, y)$$$,输入中不存在其他对 $$$(x, y)$$$ 和 $$$(y, x)$$$。

输出

打印$$$n$$$个整数,第$$$i$$$个数字应该等于程序员的数量,第$$$i$$$个程序员可以作为导师。程序员的编号顺序与输入中给出的技能顺序相同。

示例

输入 #1

4 2
10 4 10 15
1 2
4 3

输出 #1

0 0 1 2

输入 #2

10 4
5 4 1 5 4 3 7 1 2 5
4 6
2 1
10 8
3 5

输出 #2

5 4 0 5 3 3 9 0 2 5

注意

在第一个例子中,第一个程序员不能成为任何其他程序员的导师(因为只有第二个程序员拥有技能,低于第一个程序员的技能,但他们正在争吵)。第二个程序员不能成为任何其他程序员的导师,因为他的技能在其他程序员中是最少的。第三位程序员可以是第二位程序员的导师。第四个程序员可以是第一个和第二个程序员的导师。他不能成为第三个程序员的导师,因为他们正在争吵。