AT_pakencamp_2024_day2_h Hold a Contest

在 Paken 王国中有 $N$ 名居民，编号为 $1$ 到 $N$。每个居民都有一个代表竞技编程实力的评级，居民 $i$ 的评级为 $R_i$。 此外，在这 $N$ 人之间存在 $M$ 对好友关系，居民 $A_j$ 与居民 $B_j$ 之间是好友（$1 \leq j \leq M$）。除了这 $M$ 对好友关系外，没有其他的好友关系。 Pataro 决定面向 Paken 王国的居民举办竞技编程比赛。首先，他会设定一个评级限制 $X$（$X$ 为整数），然后自由选择 $K$ 名居民并发送邀请函。 收到 Pataro 或其他居民发送的邀请函的居民 $x$（$1 \leq x \leq N$）会按如下方式行动： - 如果已经收到了 $1$ 张或更多邀请函，则什么也不做。 - 如果还未收到邀请函，且自己的评级大于等于评级限制（即 $X \leq R_x$），则会参加比赛，并向自己所有的好友再次发送邀请函。 - 否则，什么也不做。 Pataro 希望尽可能提升比赛的评级限制，但如果参与人数过少则会产生困扰。 为此，Pataro 思考了 $N$ 个问题。第 $k$ ($1 \leq k \leq N$) 个问题如下： - 为了使至少 $k$ 名居民参加比赛，评级限制 $X$ 至多可以设为多少？邀请函可以自由发送给 $K$ 名居民。 请你为 Pataro 编写程序，回答这 $N$ 个问题。

输入以如下格式从标准输入给出。 > $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. （$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$ 分）无额外限制 ## 样例说明 1 例如，当 $k=3$ 时，设 $X=2$ 可以满足条件。具体来说，若给居民 $2$ 发送邀请函，居民 $2$ 会给居民 $3$ 发送邀请函，居民 $3$ 又会给居民 $4$ 发送邀请函，最终居民 $2,3,4$ 共 $3$ 人能够参赛，从而达到要求。注意，居民 $2$ 也会给居民 $1$ 发送邀请函，但居民 $1$ 的评级未达到 $X$，因此不会参赛。 该样例符合子任务 $3, 5, 6, 7, 8$ 的限制。 # 数据范围与约定 - $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$） - 输入均为整数。 由 ChatGPT 5 翻译