Задача: Wormhole Sort
Коровы Фермера Джона устали от ежедневных сортировок перед выходом из амбара. Они получили Ph.D по квантовой физике и готовы ускорить этот процесс.
Этим утром, как обычно \(N\) коров (\(1 \leq N \leq 10^5\)), последовательно пронумерованных \(1 \dots N\), находятся в амбаре на различных позициях, также пронумерованных \(1 \dots N\), так что корова \(i\) находится в позиции \(p_i\). Однако этим утром имеется \(M\) туннелей (\(1 \leq M \leq 10^5\)), которые пронумерованы \(1 \dots M\), при этом туннель \(i\) двунаправленно связывает позиции \(a_i\) и \(b_i\) и имеет ширину \(w_i\) ( \(1\le a_i,b_i\le N, a_i\neq bi, 1\le w_i\le 10^9\) ).
В любой момент времени две коровы, расположенные на противоположных концах туннеля могут параллельно поменяться позициями через него. Коровы могут таким образом меняться позициями сколько угодно раз пока корова \(i\) не окажется в позиции \(i\) для \(1 \leq i \leq N\).
Коровы не хотят быть раздавленными в туннелях. Помогите им максимизировать ширину туннеля с самой маленькой шириной, которые они должны использовать, чтобы упорядочиться
ОЦЕНИВАНИЕ:
- Тесты 3-5 удовлетворяют ограничениям \(N,M\le 1000.\)
- Тесты 6-10 не имеют дополнительных ограничений.
ФОРМАТ ВВОДА:
Первая строка содержит два целых числа \(N\) и \(M\).
Вторая строка содержит \(N\) целых чисел \(p_1, p_2, \dots, p_N\). Гарантируется, что \(p\) есть перестановка чисел \(1\ldots N.\)
Для каждого \(i\) между \(1\) и \(M\), строка \(i+2\) содержит целые числа \(a_i\), \(b_i\), и \(w_i\).
ФОРМАТ ВЫВОДА:
Одно целое число: наибольшая минимальная ширина туннеля, в которую поместится коров во время процесса сортировки. Если коровы не используют туннели во время сортировки выведите \(-1\).
Ваш ответ: