← 返回题目列表

AtCoder · pakencamp_2024_day2_h

H. 举办比赛

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

配点 : 100 点

問題文

在帕肯王国 N 有人住在那里, 它们的编号最大为1 到 N 。公园王国的居民会获得代表其竞技项目实力的评级。 i (1 \leq i \leq N) 的评级为 R_i 。

另外,这个 N 人与人之间 有 M 友谊和居民 A_j 和居民 B_j (1 \leq j \leq M) 是朋友。这个 除了 M 友谊之外,没有其他居民群体是朋友。

帕塔罗决定为帕肯王国的居民举办一场编程竞赛。首先,帕塔罗有评级限制。X (X 是一个整数),那么 N 居民 K 我随机选择了一个人并决定向他们发送邀请。

收到帕塔罗或其他居民邀请的居民。 x (1 \leq x \leq N) 的行为如下。

  • 已经 如果您已收到 1 或更多邀请,则无需执行任何操作。
  • 如果您之前没有收到过邀请,并且您的评分高于评分限制,即 X \leq R_x ,向所有参加比赛且也是您的朋友的居民发送新邀请。
  • 否则,什么都不做。

帕塔罗希望尽可能提高评分上限,以提高比赛的水平,但如果参加者太少,就会出现问题。

所以帕塔罗 我想到了 N 问题。k (1 \leq k \leq N) 问题是:

  • k 可以设置的最高评分限制是多少,以便更多居民可以参与竞赛?不过,请发送邀请 K 居民可以自由选择。

对于帕塔罗来说,这 编写一个程序来回答 N 问题。 输出为

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq R_i \leq 10^{18} (1 \leq i \leq N)
  • 1 \leq A_i<B_i \leq N (1 \leq i \leq M)
  • (A_i,B_i) \neq (A_j,B_j) (i \neq j)
  • 所有输入均为整数

小課題

  1. (1 点) N \leq 2
  2. (2 点) M = 0
  3. (2 点) N \leq 10
  4. (10 点) R_i = 1 (1 \leq i \leq N)
  5. (10 点) R_i \leq 5 (1 \leq i \leq N)
  6. (20 点) K = 1
  7. (30 点) K \leq 5
  8. (25 点)无附加约束

入力

输入将以以下形式从标准输入给出。

N M K
R_1 R_2 \ldots R_N
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

标准输出为 N 行。 以整数形式打印第 k 行中,k 个问题的答案。但是,无论您如何设置评级限制, k 如果超过一名居民无法参加比赛,-1 。


入力例 1

4 3 1
1 2 3 4
1 2
2 3
3 4

出力例 1

4
3
2
1

例如, k=3 时, 当您移动到 X=2 可以满足条件。具体来说,居民 如果您向 2 发送邀请,居民 2 是居民 3 的居民 为了向 3 是居民 4 发送邀请,居民 2,3,4 的 3 当人们参与时就满足条件。此外,居民 2 是居民 我们还将向 1 发送邀请,但居民 居民,因为它小于 1 的评级为 X 居民,因为它小于 1 不会参加比赛。

此示例是一个小作业。 3, 5, 6, 7, 8 约束。


入力例 2

4 0 2
4 3 2 1

出力例 2

4
3
-1
-1

此示例是一个小作业。 2, 3, 5, 7, 8 约束。


入力例 3

4 2 2
1 1 1 1
1 3
2 4

出力例 3

1
1
1
1

此示例是一个小作业。 3, 4, 5, 7, 8 约束。