Родина Феникса, Страна Огня, состоит из \(n\) городов, которые были соединены \(m\) дорогами, но из-за землетрясения они все были разрушены. Теперь Страна Огня хочет восстановить \(n-1\) из этих дорог так, чтобы все города стали снова связаны.
Первоначально, в \(i\)-м городе есть \(a_i\) тонн асфальта. Чтобы восстановить дорогу, необходимо \(x\) тонн асфальта. При этом, чтобы восстановить дорогу между городами \(i\) и \(j\), в городах \(i\) и \(j\) должно быть суммарно хотя бы \(x\) тонн асфальта. Другими словами, в городе \(i\) есть \(a_i\) тонн асфальта, а городе \(j\) — \(a_j\) тонн, то после восстановления дороги между ними останется \(a_i+a_j-x\) тонн. Асфальт можно перевозить между городами, если дорога между ними уже восстановлена.
Определите, возможно ли связать все города, и если да, то выведите последовательность дорог, которые нужно восстановить, в соответствующем порядке.
Выходные данные
Если невозможно связать все города, выведите 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\) используют свой асфальт вместе для постройки дороги. В каждом городе по \(1\) тонне, то есть вместе \(2\) тонны, чего достаточно.
В третьем примере, для восстановления дороги между городами \(1\) и \(2\) асфальта недостаточно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4 1
0 0 0 4 0
1 2
2 3
3 4
4 5
|
YES
3
2
1
4
|
|
2
|
2 1 2
1 1
1 2
|
YES
1
|
|
3
|
2 1 2
0 1
1 2
|
NO
|
|
4
|
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
|