Laiko ribojimas: 1s

Atminties ribojimas: 128MB

Duomenų failas: slidkur2.in

Rezultatų failas: slidkur2.out

Jei norite pateikti savo sprendimą - prisijunkite.

Slidinėjimo kurortas 2

Rengiamame slidinėjimo kurorte jau yra numatytos trasos, kurias sudaro M čiuožimo atkarpų, jungiančių N taškų. Kiekvienam taškui žinome jo aukštį virš jūros lygio H_i. Atkarpomis galima čiuožti tik nuo aukštesnio taško link žemesnio. Taškų aibė yra jungi, t. y. jei galėtume čiuožti abiejomis atkarpų kryptimis, galėtume iš kiekvieno taško patekti į bet kurį kitą.

Jūsų tikslas yra suprojektuoti keltuvų lynus taip, kad būtų įmanoma iš bet kurio iš N taškų patekti į bet kurį kitą. Lynas jungia du taškus A ir B, kur H_A\\leqH_B. Šiuo lynu galima nukeliauti tik viena kryptimi – iš A į B.

Kad būtų mažesnės išlaidos, pasirinkite tokį variantą, kad visų lynų galų aukščių skirtumų suma S=\\sum_{i=1}^{L}H_{B_i}-H_{A_i} būtų kiek įmanoma mažesnė. Jei vis dar yra keli variantai, pasirinkite tokį, kad bendras lynų kiekis L būtų minimalus. Jei ir tokių variantų yra keli, išveskite bet kurį.

Pradiniai duomenys

Pirmoje eilutėje – skaičiai N ir M (1\\leqN\\leq100, 1\\leqM\\leq10~000).

Antroje eilutėje – N skaičių H_i (0\\leqH_i\\leq10~000). Visi aukščiai yra skirtingi.

Kitose M eilučių yra po skirtingą porą skaičių U_i ir V_i, žyminčių čiuožimo atkarpas (1\\leqU_i,V_i\\leqN, H_{U_i}>H_{V_i}

Rezultatai

Pirmoje eilutėje išveskite skaičių S, antroje eilutėje – skaičių L. Kitose L eilučių išveskite taškų poras A_i ir B_i – lynais sujungiamus taškus.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
4 3
100 80 60 0
1 2
2 3
2 4
 
100
2
3 1
4 3