Злі корови#10664

Злі корови

6 секунд

256 мегабайтів

Середня

Останніми роками спостерігається швидке поширення Extremely Green Oxen Illness (EGOI) — хвороби, що робить корів небезпечними для туристів. Після кількох інцидентів було вирішено, що ми маємо відокремити райони, де пасуться корови, від районів, де ходять туристи.

У вас є карта Альп. На карті є $n$ районів. Кожен з районів може бути або населений коровами, або туристичним, або пустим. Деякі пари цих районів з'єднані двонаправленими дорогами. Кожна дорога має невід'ємну довжину. (Мовою теорії графів, карта — це неорієнтований граф із зваженими ребрами.)

Ви можете побудувати стіни в деяких районах. Як тільки ви будуєте стіну в районі, цей район стає недоступним для корів та туристів — вони більше не зможуть проходити через цей район.

Ваше завдання — вибрати набір районів, де будуть побудовані стіни. Цей набір районів має задовольняти наступні умови:

Він має складатися лише з пустих районів.
Він має відокремлювати райони з коровами від туристичних. Отже, корови не повинні мати можливість пройти по дорогах до туристичного району (без проходження через райони зі стінами).
Він не має відокремлювати туристичні райони один від одного. Отже, туристи повинні мати можливість пройти по дорогах від будь-якого туристичного району до будь-якого іншого туристичного району (без проходження через райони зі стінами).

Якщо є декілька варіантів, як досягти описаної вище мети, нас буде хвилювати лише простота обслуговування стін. Стіни будуть утримуватись спеціальними бригадами. Існує рівно одна така бригада в кожному з туристичних районів.

Для будь-якого району $A$ ми визначаємо його віддаленість як мінімальну довжину шляху між $A$ та деяким туристичним районом. (Довжина шляху — це сума довжин доріг. Зверніть увагу, що шлях може проходити через стіни та райони з коровами — бригада, що обслуговує стіну, має усі можливості та засоби, щоб здійснити такий рух.)

Віддаленість набору районів — це максимальна віддаленість будь-якого району в цьому наборі.

Серед усіх наборів районів зі стінами, що задовольняють усі наведені умови, знайдіть та поверніть набір із найменшою можливою віддаленістю. Якщо існує декілька таких наборів, поверніть будь-який із них.

Зверніть увагу, що кількість вибраних районів не грає ролі. Тобто, не обов'язково використовувати мінімальну кількість стін.

Вхідні дані

Перший рядок містить два цілі числа $n$ та $m$ ( $2 \leq n \leq 3 \cdot 1 0^{5}$ 2 \leq n \leq 3 \cdot 10^5, $n - 1 \leq m \leq 3 \cdot 1 0^{5}$ n - 1 \leq m \leq 3 \cdot 10^5) — кількість районів та доріг відповідно. Райони пронумеровані від $1$ до $n$ .

Другий рядок містить $n$ цілих чисел $t_{1}, \dots, t_{n}$ t_1, \ldots, t_n, де $t_{i}$ t_i рівне $- 1$ , якщо $i$ -й район населений коровами, $0$ , якщо пустий, та $1$ , якщо це туристичний район.

Останні $m$ рядків описують дороги. $j$ -й із них містить три цілі числа $a_{j}$ a_j, $b_{j}$ b_j та $ℓ_{j}$ \ell_j ( $1 \leq a_{j} < b_{j} \leq n$ 1 \leq a_j < b_j \leq n, $0 \leq ℓ_{j} \leq 1 0^{9}$ 0 \leq \ell_j \leq 10^9), що позначають дорогу між районами $a_{j}$ a_j та $b_{j}$ b_j довжини $ℓ_{j}$ \ell_j.

Гарантується, що:

між будь-якими двома районами є не більше однієї дороги,
в даний момент можливо пройти між будь-якими двома районами, використовуючи $0$ або більше доріг,
існує щонайменше один район, населений коровами,
існує щонайменше один туристичний район.

Вихідні дані

Якщо неможливо побудувати стіни, як вказано в умові, виведіть -1.

Інакше перший рядок має містити число $k$ — кількість районів, де ви хочете побудувати стіни. Другий рядок має містити $k$ цілих чисел — номери районів, де ви хочете побудувати стіни. (Ці номери мають бути різними числами від $1$ до $n$ включно. Вони не обов'язково мають бути в певному порядку.)

Ваш вивід буде прийнятий, якщо набір підходить під умови та він із мінімальною віддаленістю.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

В усіх прикладах блакитний колір використовується для туристичних районів, коричневий — для районів, населених коровами, та оранжевий — для стін.

У першому прикладі мінімальна можлива віддаленість рівна $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 \leq 10$ n \leq 10.

Блок $2$ ( $22$ бали): усі довжини $ℓ_{j} = 0$ \ell_j = 0.

Блок $3$ ( $16$ балів): існує рівно один туристичний район.

Блок $4$ ( $11$ балів): існує рівно $n - 1$ n - 1 доріг (мовою теорії графів, заданий граф є деревом).

Блок $5$ ( $8$ балів): $n, m \leq 2000$ n, m \leq 2000 та усі довжини $ℓ_{j} = 1$ \ell_j = 1.

Блок $6$ ( $36$ балів): без додаткових обмежень.