配点 : 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 点) N \leq 2
- (2 点) M = 0
- (2 点) N \leq 10
- (10 点) R_i = 1 (1 \leq i \leq N)
- (10 点) R_i \leq 5 (1 \leq i \leq N)
- (20 点) K = 1
- (30 点) K \leq 5
- (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 约束。