Qurd Dəlikləri ilə Sıralama#9601

Qurd Dəlikləri ilə Sıralama

2 saniyə

128 meqabayt

Çox asan

Farmer John-un inəkləri onun hər sübh tövlədən çıxmazdan əvvəl sıralanmaq tələbindən yorulmuşdular. Onlar yaxınlarda kvant fizikası üzrə PhD dərəcəsi almışdılar və bu prosesi bir az sürətləndirməyə hazırdırlar.

Bu gün səhər, adətən olduğu kimi, Farmer John-un rahatlıq üçün $1... n$ ilə nömrələnmiş $n$ inəyi tövlədə, həmçinin $1... n$ ilə nömrələnmiş $n$ müxtəlif yerdə yerləşir, belə ki, $i$ inəyi $p_{i}$ p_i yerində yerləşir. Lakin bu gün səhər tövlədə həmçinin $1... m$ ilə nömrələnmiş $m$ qurd dəliyi var. $i$ qurd dəliyi $a_{i}$ a_i və $b_{i}$ b_i yerlərini ikitərəfli birləşdirir və $w_{i}$ w_i enə malikdir.

İstənilən anda qurd dəliyinin qarşı tərəflərində olan iki inək bu qurd dəliyi vasitəsilə hərəkət edərək eyni zamanda yerlərini dəyişə bilər. İnəklər hər $1 \leq i \leq n$ 1 \leq i \leq n üçün $i$ inəyi $i$ yerində olana qədər belə dəyişmələr etməlidirlər.

İnəklər çox dar qurd dəliklərinə sıxılıb qalmaq istəmirlər. Sıralama üçün istifadə etmələri lazım olan bütün qurd dəliklərinin arasında minimum eni maksimallaşdırmağa onlara kömək edin.

Giriş

Birinci sətirdə iki tam ədəd $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) və $m (1 \leq m \leq 1 0^{5})$ m~(1 \le m \le 10^5) verilmişdir.

İkinci sətirdə $n$ tam ədəd $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n verilmişdir. $p$ -nin $1... n$ ədədlərinin permutasiyası olduğu təmin edilir.

$1$ -dən $m$ -ə qədər hər bir $i$ üçün $i + 2$ i + 2 sətrində $a_{i}, b_{i}$ a_i, b_i və $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) tam ədədləri verilmişdir.

Çıxış

Bir tam ədəd çap edin: sıralama prosesində istifadə olunan bütün qurd dəliklərinin arasında minimum eninin mümkün olan maksimum qiyməti. Əgər inəklərin sıralama üçün heç bir qurd dəliyindən istifadə etməsinə ehtiyac yoxdursa, $- 1$ çap edin.

Nümunələr

Yalnız eni $9$ -dan az olmayan qurd dəliklərindən istifadə edərək inəkləri sıralamağın mümkün üsullarından biri budur:

$1$ inəyi və $2$ inəyi üçüncü qurd dəliyi vasitəsilə yerlərini dəyişirlər.
$1$ inəyi və $3$ inəyi birinci qurd dəliyi vasitəsilə yerlərini dəyişirlər.
$2$ inəyi və $3$ inəyi üçüncü qurd dəliyi vasitəsilə yerlərini dəyişirlər.

Nümunə 1

Nümunə 2