Останніми роками спостерігається швидке поширення Extremely Green Oxen Illness (EGOI) — хвороба, що робить корів небезпечними для туристів. Після кількох інцидентів було вирішено, що ми маємо відокремити райони, де пасуться корови від районів, де ходять туристи.
У вас є карта Альп. На карті є n районів. Кожен з районів може бути або населений коровами, або туристичним, або пустим. Деякі пари цих районів з'єднані двонаправленими дорогами. Кожна дорога має невід'ємну довжину. (Мовою теорії графів, карта це неорієнтовний граф з зваженими ребрами.)
Ви можете побудувати стіни в деяких районах. Як тільки Ви будуєте стіну в районі, цей район стає недоступним для корів та туристів — вони більше не зможуть проходити через цей район.
Ваше завдання — вибрати набір районів, де будуть побудовані стіни. Цей набір районів має задовольняти наступні умови:
Він має складатись лише з пустих районів.
Він має відокремлювати райони з коровами від туристичних. Отже, корови не повинні мати можливість пройти по дорогах до туристичного району (без проходження через райони з стінами).
Він не має відокремлювати туристичні райони один від одного. Отже, туристи повинні мати можливість пройти по дорогах від будь-якого туристичного району до будь-якого іншого туристичного району (без проходження через райони з стінами).
Якщо є декілька варіантів, як досягти описаної вище мети, ми будемо хвилюватись лише про простоту обслуговування стін. Стіни будуть утримуватись спеціальними бригадами. Існує рівно одна така бригада в кожному з туристичних районів.
Для будь-якого району A ми визначаємо його віддаленість як мінімальну довжину шляху між A та деяким туристичним районом. (Довжина шляху це сума довжин доріг. Зверніть увагу, що шлях може проходити через стіни та райони з коровами — бригада, що обслуговує стіну, має усі можливості та знаряддя, щоб здійснити такий рух.)
Віддаленість набору районів це максимальна віддаленість будь-якого району в цьому наборі.
Серед усіх наборів районів з стінами, що задовольняють усі наведені умови, знайдіть та поверніть набір з найменшою можливою віддаленістю. Якщо існує декілька таких наборів, поверніть будь-який з них.
Зверніть увагу, що кількість вибраних районів не грає ролі. Тобто, не обов'язково використовувати мінімальну кількість стін.
Перший рядок містить два цілі числа n та m (2≤n≤3⋅105, n−1≤m≤3⋅105) — кількість районів та доріг відповідно. Райони пронумеровані від 1 до n.
Другий рядок містить n цілих чисел t1,...,tn, де ti рівне −1, якщо i-й район населений коровами, 0, якщо пустий, та 1, якщо це туристичний район.
Останні m рядків описують дороги. j-й з них містить три цілі числа aj, bj та ℓj (1≤aj<bj≤n, 0≤ℓj≤109), що позначають дорогу між районами aj та bj довжини ℓj.
Гарантується, що:
між будь-якими двома районами є не більше однієї дороги,
в даний момент можливо пройти між будь-якими двома районами, використовуючи 0 або більше доріг,
існує щонайменше один район, населений коровами,
існує щонайменше один туристичний район.
Якщо неможливо побудувати стіни, як вказано в умові, виведіть -1
.
Інакше, перший рядок має містити число k — кількість доріг, які Ви хочете побудувати. Другий рядок має містити k цілих чисел — номери районів, де Ви хочете побудувати стіни. (Ці номери мають бути різними числами від 1 до n, включно. Вони не обов'язково мають бути в певному порядку.)
Ваш вивід буде прийнятий, якщо набір підходить під умови та він з мінімальною віддаленістю.
В усіх прикладах, блакитний колір використовується для туристичних районів, коричневий для районів, населених коровами, та оранжевий для стін.
У першому прикладі, мінімальна можлива віддаленість рівна 2, що досягається розміщенням доріг в райони 4, 5 та 6. Зверніть увагу, що ми не можемо розмістити стіни в районах 4, 2 та 6, навіть отримуючи віддаленість 1, бо тоді буде неможливо пройти між туристичними районами 1 та 3 без проходження через стіни.
У другому прикладі, віддаленість району 2 рівна 1000, віддаленість району 3 рівна 30, оскільки це може бути досягнуто по шляху 1–5–4–3. (Нагадуємо, що бригади можуть проходити через стіни та районів з коровами). Отже, ми маємо розмістити стіни в районах 5 та 3 (не 2), і тоді віддаленість буде рівна 30.
Блок 1 (7 балів): n≤10.
Блок 2 (22 бали): усі довжини ℓj=0.
Блок 3 (16 балів): існує рівно один туристичний район.
Блок 4 (11 балів): існує рівно n−1 доріг (мовою теорії графів, заданий граф є деревом).
Блок 5 (8 балів): ми маємо n,m≤2000 та усі довжини ℓj=1.
Блок 6 (36 балів): без додаткових обмежень.