CF1515F Phoenix and Earthquake

凤凰的故乡火之国有 $n$ 个城市，这些城市通过 $m$ 条道路相连，但一场地震摧毁了所有道路。火之国希望修复其中的 $n-1$ 条道路，使得所有城市重新连通。 第 $i$ 个城市拥有 $a_i$ 吨沥青。修复一条道路需要消耗 $x$ 吨沥青，并且要修复城市 $i$ 和城市 $j$ 之间的道路，城市 $i$ 和 $j$ 的沥青总量至少要有 $x$ 吨。也就是说，如果城市 $i$ 有 $a_i$ 吨沥青，城市 $j$ 有 $a_j$ 吨沥青，那么修复这条道路后，两城剩余沥青为 $a_i + a_j - x$ 吨。若两城市之间的道路已修复，则沥青可以在两城市间自由转移。 请判断是否有可能使所有城市连通。如果可以，请输出任意一种修复道路的顺序。

第一行包含三个整数 $n$、$m$ 和 $x$（$2 \le n \le 3 \cdot 10^5$；$n-1 \le m \le 3 \cdot 10^5$；$1 \le x \le 10^9$），分别表示城市数量、道路数量和修复一条道路所需的沥青量。 第二行包含 $n$ 个用空格分隔的整数 $a_i$（$0 \le a_i \le 10^9$），表示每个城市初始拥有的沥青量。 接下来 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$x_i \ne y_i$；$1 \le x_i, y_i \le n$），表示第 $i$ 条道路连接的两个城市。保证每对城市之间至多有一条道路，且地震前城市间是连通的。

如果无法连通所有城市，输出 NO。否则，输出 YES，并在下一行输出 $n-1$ 个整数 $e_1, e_2, \dots, e_{n-1}$，表示修复道路的顺序。$e_i$ 表示第 $i$ 次修复的道路编号。如果有多种方案，输出任意一种均可。

在第一个样例中，道路修复顺序如下： - 首先修复第 $3$ 条道路，连接城市 $3$ 和 $4$。城市 $4$ 原有 $4$ 吨沥青，修复后剩 $3$ 吨。 - 然后修复第 $2$ 条道路，连接城市 $2$ 和 $3$。城市 $4$ 的沥青可以转移到城市 $3$ 并用于修路，修复后剩 $2$ 吨。 - 接着修复第 $1$ 条道路，连接城市 $1$ 和 $2$。沥青转移到城市 $2$ 并用于修路，修复后剩 $1$ 吨。 - 最后修复第 $4$ 条道路，连接城市 $4$ 和 $5$。沥青转移到城市 $4$ 并用于修路，修复后沥青用尽。 此时所有城市均已连通。 在第二个样例中，城市 $1$ 和 $2$ 合计有 $2$ 吨沥青，足以修复道路。 在第三个样例中，城市 $1$ 和 $2$ 的沥青总量不足，无法连通。 由 ChatGPT 4.1 翻译