F. Феникс и землетрясение
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Родина Феникса, Страна Огня, состоит из $$$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$$$-й в порядке восстановления дороги. Если существует несколько ответов, выведите любой.

Примеры
Входные данные
5 4 1
0 0 0 4 0
1 2
2 3
3 4
4 5
Выходные данные
YES
3
2
1
4
Входные данные
2 1 2
1 1
1 2
Выходные данные
YES
1
Входные данные
2 1 2
0 1
1 2
Выходные данные
NO
Входные данные
5 6 5
0 9 4 0 10
1 2
1 3
2 3
3 4
1 4
4 5
Выходные данные
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$$$ асфальта недостаточно.