Сортування червоточин#9601

Сортування червоточин

2 секунди

128 мегабайтів

Дуже легка

Корови фермера Джона втомилися від його щоденної вимоги сортуватися перед тим, як щоранку залишити хлів. Вони щойно отримали degrees PhD з квантової фізики та готові трохи прискорити цей процес.

Сьогодні вранці, як звичайно, $n$ корів фермера Джона, зручно пронумерованих від $1... n$ , знаходяться в хліві в $n$ різних місцях, також пронумерованих від $1... n$ , причому корова $i$ знаходиться в місці $p_{i}$ p_i. Однак сьогодні вранці в хліві також є $m$ червоточин, пронумерованих від $1... m$ . Червоточина $i$ двонапрямлено з'єднує місця $a_{i}$ a_i та $b_{i}$ b_i і має ширину $w_{i}$ w_i.

У будь-який момент часу дві корови, що знаходяться на протилежних кінцях червоточини, можуть одночасно поміняти місцями, перемістившись через цю червоточину. Корови повинні виконувати такі обміни до тих пір, поки для кожної $1 \leq i \leq n$ 1 \leq i \leq n корова $i$ не опиниться в місці $i$ .

Корови не хочуть застрягати в занадто вузьких червоточинах. Допоможіть їм максимізувати мінімальну ширину серед усіх червоточин, які їм знадобиться використовувати для сортування.

Вхідні дані

У першому рядку знаходяться два цілих числа $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) і $m (1 \leq m \leq 1 0^{5})$ m~(1 \le m \le 10^5).

У другому рядку знаходяться $n$ цілих чисел $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n. Гарантується, що $p$ є перестановкою чисел $1... n$ .

Для кожного $i$ від $1$ до $m$ у рядку $i + 2$ i + 2 знаходяться цілі числа $a_{i}, b_{i}$ a_i, b_i та $w_{i} (1 \leq a_{i}, b_{i} \leq n, a_{i} \neq = b_{i}, 1 \leq w_{i} \leq 1 0^{9})$ w_i~(1 \le a_i, b_i \le n, a_i \neq b_i, 1 \le w_i \le 10^9).

Вихідні дані

Виведіть одне ціле число: максимально можливе значення мінімальної ширини серед усіх червоточин, використаних у процесі сортування. Якщо коровам не потрібно використовувати жодної червоточини для сортування, виведіть $- 1$ .

Приклади

Ось один із можливих способів відсортувати корів, використовуючи лише червоточини шириною не менше $9$ :

Корова $1$ і корова $2$ міняються місцями за допомогою третьої червоточини.
Корова $1$ і корова $3$ міняються місцями за допомогою першої червоточини.
Корова $2$ і корова $3$ міняються місцями за допомогою третьої червоточини.

Приклад 1

Приклад 2