← 返回题单

题单练习挑战赛普及/提高- 题

← 上一题下一题 →

A1789 | $拳击教练$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

在一个拳击爱好者的网站中，有 $n$ 名拳击选手的资料，第 $i$ 位选手有能力值 $ri$。 当选手 $a$ 的能力值 大于 选手 $b$ 的能力值时，$a$ 可以成为 $b$ 的教练，但如果 $a$ 选手 与 $b$ 选手是死对头，$a$ 就无法成为 $b$ 的教练。 现在给你 $n$ 个选手的能力值，以及 $k$ 对选手，为死对头的关系。 对于每一个选手，他可以成为成为多少个选手的教练。

输入格式

第一行输入两个数，$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}))$，代表选手的个数，以及有 $k$ 对选手是死对头。 第二行包含 $n$ 个整数，$r_1, r_2, \dots, r_n$ $(1 \le r_i \le 10^{9})$，其中 $ri$ 是第 $i$ 个选手的能力值。 接下来有 $k$ 行，每一行有两个数 $a$，$b$，表示 $a$ 与 $b$ $(1 \leq a,b \leq n，a \neq b)$ 是死对头。

输出格式

输出 $n$ 个数，按输入的顺序，输出每位选手能成为多少人的教练。

输入输出样例

输入 #1

输出 #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

C++ 编辑器

输入

输出