Zəhərli inəklər#10664
Son illərdə Extremely Green Oxen Illness (EGOI) — turistlər üçün təhlükəli hala gətirən inək xəstəliyi — sürətlə yayılır. Bir neçə insidentdən sonra qərara alındı ki, inəklərin otladığı əraziləri turistlərin gəzdiyi ərazilərdən ayırmaq lazımdır.
Sizin ixtiyarınızda Alp dağlarının xəritəsi var. Xəritədə rayon var. Hər bir rayon ya inəklərlə doludur, ya turistikdir, ya da boşdur. Bəzi rayon cütləri arasında iki istiqamətli yollar var. Hər yolun mənfi olmayan uzunluğu var. (Qraf nəzəriyyəsi dili ilə desək, xəritə çəkili qıvrımları olan istiqamətsiz qrafdır.)
Bəzi rayonlarda divar tikə bilərsiniz. Divar tikilən rayon həm inəklər, həm də turistlər üçün əlçatmaz olur — onlar artıq bu rayondan keçə bilməzlər.
Sizin vəzifəniz — divar tikəcəyiniz rayonların dəstini seçməkdir. Bu rayon dəsti aşağıdakı şərtləri təmin etməlidir:
Yalnız boş rayonlardan ibarət olmalıdır.
İnəklərlə dolu rayonları turistik rayonlardan ayırmalıdır. Yəni, inəklər heç bir halda (divar tikilən rayonlardan keçmədən) turistik rayonlara yollarla çatmamalıdır.
Turistik rayonları bir-birindən ayırmamalıdır. Yəni, istənilən iki turistik rayon arasında (divar tikilən rayonlardan keçmədən) yollarla keçid qalmalıdır.
Əgər bu məqsədə nail olmağın bir neçə yolu varsa, yalnız divarların xidmət baxımından rahatlığı narahatlıq doğuracaq. Divarları xüsusi briqadalar xidmət edəcək. Hər bir turistik rayonda məhz bir belə briqada var.
Hər hansı bir rayonu üçün onun uzaqlığı ən qısa yolun (yolun uzunluğu, yolların cəmi) ilə hansısa turistik rayon arasında olan minimal uzunluq kimi hesablanır. (Qeyd: bu yol divarlardan və inəklər olan rayonlardan keçə bilər — divar briqadalarının hərəkət imkanları və vasitələri var.)
Rayonlar dəstinin uzaqlığı o dəstdəki istənilən rayonun maksimal uzaqlığıdır.
Yuxarıda göstərilən bütün şərtlərə cavab verən rayon dəstləri içərisində minimal mümkün uzaqlığa malik olan dəsti tapın və qaytarın. Əgər belə dəst bir neçədirsə, istənilənini qaytara bilərsiniz.
Qeyd: Seçilən rayonların sayı vacib deyil, yəni mütləq minimal sayda divar qoymaq tələb olunmur.
Birinci sətirdə iki tam ədəd və (2 \leq n \leq 3 \cdot 10^5, n-1 \leq m \leq 3 \cdot 10^5) — rayonların və yolların sayı verilir. Rayonlar -dən -ə kimi nömrələnib.
İkinci sətirdə tam ədəd t_1, ..., t_n verilir, burada t_i = -1 — -ci rayon inəklərlə doludursa, — boşdursa, — turistik rayondursa.
Son sətirdə yollar təsvir olunur. -ci sətirdə üç tam ədəd a_j, b_j, \ell_j (1 \le a_j < b_j \le n, 0 \le \ell_j \le 10^9) verilib — a_j və b_j rayonları arasında uzunluğu \ell_j olan yol.
Qarantiya verilir ki:
istənilən iki rayon arasında ən çox bir yol var,
istənilən iki rayon arasında 0 və ya daha çox yol vasitəsilə keçmək mümkündür,
ən azı bir inəklə dolu rayon var,
ən azı bir turistik rayon var.
Əgər divarları şərtlərdə göstərildiyi kimi qoymaq mümkün deyilsə, -1 çıxış edin.
Əks halda, birinci sətirdə — tikmək istədiyiniz divarların sayı olmalıdır. İkinci sətirdə isə fərqli ədəd — divar tikəcəyiniz rayonların nömrələri olmalıdır. (Bu ədədlər -dən -ə qədər fərqli ədədlərdir və ardıcıllıq istənilən ola bilər.)
Çıxışınız qəbul olunacaq, əgər dəst şərtlərə cavab verirsə və uzaqlığı minimaldır.
Nümunə 1
Nümunə 2
Nümunə 3
Bütün nümunələrdə göy rəng turistik rayonları, qəhvəyi inək rayonlarını, narıncı isə divarlardır.
Birinci nümunədə minimal mümkün uzaqlıq 2-dir, bu da divarların 4, 5 və 6-cı rayonlara yerləşdirilməsi ilə əldə olunur. Qeyd edək ki, 4, 2 və 6-cı rayonlara divar yerləşdirmək olmaz, çünki bu halda 1 və 3-cü turistik rayonlar arasında divarsız keçid qalmır, uzaqlıq isə 1 olsa belə.
İkinci nümunədə 2-ci rayon üçün uzaqlıq 1000, 3-cü rayon üçün 30-dur, çünki bu 1–5–4–3 yolu ilə alınır. (Xatırladaq ki, briqadalar divarlardan və inək rayonlarından keçə bilər.) Buna görə divarları 5 və 3-cü rayonlarda (2-də deyil) yerləşdirmək lazımdır və onda uzaqlıq 30 olacaq.
Blok 1 (7 bal): n \le 10.
Blok 2 (22 bal): bütün \ell_j = 0.
Blok 3 (16 bal): yalnız bir turistik rayon var.
Blok 4 (11 bal): yalnız n-1 yol var (yəni qraf ağacdır).
Blok 5 (8 bal): n, m \le 2000 və bütün uzunluqlar \ell_j = 1.
Blok 6 (36 bal): əlavə məhdudiyyətsiz.