Коровы Фермера Джона устали от ежедневных сортировок перед выходом из амбара.
Они получили 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 ai,bi\le N,
ai\neq bi, 1\le wi\le 10^9$).
В любой момент времени две коровы, расположенные на противоположных концах
туннеля могут параллельно поменяться позициями через него. Коровы могут
таким образом меняться позициями сколько угодно раз пока корова \(i\) не
окажется в позиции \(i\) для \(1 \leq i \leq N\).
Коровы не хотят быть раздавленными в туннелях. Помогите им максимизировать
ширину туннеля с самой маленькой шириной, которые они должны использовать,
чтобы упорядочиться
ОЦЕНИВАНИЕ:
- Тесты 3-5 удовлетворяют ограничениям \(N,M\le 1000.\)
- Тесты 6-10 не имеют дополнительных ограничений.
ФОРМАТ ВВОДА (файл wormsort.in):
Первая строка содержит два целых числа
\(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\).
ФОРМАТ ВЫВОДА (файл wormsort.out):
Одно целое число: наибольшая минимальная ширина туннеля, в которую поместится
коров во время процесса сортировки. Если коровы не используют туннели во время
сортировки выведите \(-1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
3 2 1 4
1 2 9
1 3 7
2 3 10
2 4 3
|
9
|