菲尼克斯的故乡,火烈国拥有 $$$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$$$) — 城市 $$$i$$$ 最初的沥青量。
接下来的 $$$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$$$ 条待修复道路的索引。如果有多个解决方案,请打印其中一个。
示例
输入 #1
5 4 1 0 0 0 4 0 1 2 2 3 3 4 4 5
输出 #1
YES 3 2 1 4
输入 #2
2 1 2 1 1 1 2
输出 #2
YES 1
输入 #3
2 1 2 0 1 1 2
输出 #3
NO
输入#4
5 6 5 0 9 4 0 10 1 2 1 3 2 3 3 4 1 4 4 5
输出#4
YES 6 4 1 2
注意
在第一个示例中,道路按以下顺序修复:
- 道路 $$$3$$$ 已修复,连接城市 $$$3$$$ 和 $$$4$$$。城市 $$$4$$$ 最初有 $$$4$$$ 吨沥青。这条路建成后,剩余$$$3$$$吨。
- 道路 $$$2$$$ 已修复,连接城市 $$$2$$$ 和 $$$3$$$。来自城市$$$4$$$的沥青可以运输到城市$$$3$$$并用于道路。剩余$$$2$$$ 吨。
- 道路 $$$1$$$ 已修复,连接城市 $$$1$$$ 和 $$$2$$$。沥青被运输到城市 $$$2$$$ 并用于道路。剩余$$$1$$$吨。
- 道路 $$$4$$$ 已修复,连接城市 $$$4$$$ 和 $$$5$$$。沥青被运到城市 $$$4$$$ 并用于道路。没有留下任何沥青。
在第二个示例中,城市 $$$1$$$ 和 $$$2$$$ 一起使用所有沥青来修建道路。他们每个人都有 $$$1$$$ 吨,所以他们总共有 $$$2$$$ 吨,这就足够了。
在第三个示例中,没有足够的沥青来连接城市 $$$1$$$ 和 $$$2$$$。