E. Colonization Assessment for Terraforming
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

在公元 2230 年，地球联合国准备启动 CAT 计划（Colonization Assessment for Terraforming），在 A 星系寻找可能的殖民地。

该星系中有 $$$n$$$ 个候选星球，第 $$$i$$$ 颗星球的宜居度为 $$$w_i$$$。与此同时，还有 $$$m$$$ 条双向航道连接这些星球，第 $$$i$$$ 条航道连接 $$$u_i$$$ 和 $$$v_i$$$ 两颗星球。

你作为地球联合国科研人员，需要选择出 $$$k$$$ 个星球，使得这组星球相互连通（即任意两个选择出的星球可以通过航道直接或间接到达，并且途中不能经过未选择的星球），使得这 $$$k$$$ 个星球中宜居度最小的星球的宜居度尽可能大。

Input

第一行包含一个整数 $$$T$$$（$$$1 \le T \le 1000$$$）代表数据组数。对于每组数据：

  • 第一行包含三个正整数 $$$n, m, k$$$（$$$1 \le k \le n \leq 10^5, 0 \le m \le 10^5$$$）分别代表星球数、航道数和需要选择的星球数量。
  • 下一行包含 $$$n$$$ 个正整数 $$$w_1, w_2, w_3, \cdots, w_n$$$（$$$1 \le v_i \le 10^9$$$），分别表示这 $$$n$$$ 颗星球的宜居度。
  • 接下来的 $$$m$$$ 行，第 $$$i$$$ 行包含两个整数 $$$u_i, v_i$$$（$$$1 \le u_i, v_i \le n$$$），表示第 $$$i$$$ 条航道连接的两颗星球。

保证多组数据的 $$$n$$$ 之和与 $$$m$$$ 之和均不超过 $$$2 \times 10^5$$$。

Output

对于每组数据：

  • 输出一行，包含一个整数，代表最小宜居度的最大值；如果无法选出 $$$k$$$ 个可以相互到达的星球，请输出 $$$-1$$$。
Example
Input
3
3 3 2
2 3 4
1 2
2 3
3 1
5 8 3
4 8 6 3 5
2 4
4 3
4 5
3 5
2 3
3 2
2 1
3 4
3 1 3
1 2 3
1 2
Output
3
5
-1