Arborele frumos

Ana are un arbore foarte frumos... Atât de frumos, încât încearcă să îl păstreze doar pentru ea. Cu toate acestea, Bogdan este un prieten foarte bun de-al Anei, și auzind de acest arbore frumos, a reușit să o convingă pe Ana să îi dezvăluie câteva noduri din acesta.

Arborele Anei este format din $N$ noduri, iar nodul $i$ din arbore are un coeficient de frumusețe $v_i$. Ana îi va trimite lui Bogdan poze cu $K$ din cele $N$ noduri. Apoi, se va preface că acestea au fost șterse din arbore, împreună cu muchiile lor. Apoi, se va uita la fiecare componentă conexă rămasă, și va calcula suma coeficienților de frumusețe a nodurilor din ea. Pe urmă, se definește costul de selecție al celor $K$ noduri ca fiind valoarea maximă a acestor sume.

Cerință

Totuși, Ana își dorește ca, în continuare, părțile mai frumoase din arbore să rămână nevăzute. Din acest motiv, ea caută o selecție de exact $K$ noduri care să minimizeze costul de selecție. Nefiind așa de sigură de selecția optimă, aceasta vă transmite vouă o descriere legată de cum arată arborele, împreună cu coeficienții săi de frumusețe, și vă roagă să aflați costul de selecție minim, cât și o selecție care îl obține.

Date de intrare

Pe prima linie se află numerele $N$ și $K$, cu semnificațiile descrise mai sus. Pe a doua linie se vor afla $N$ numere, al $i$-lea reprezentând coeficientul de frumusețe al nodului $i$. Pe următoarele $N$ linii, se vor afla două numere $u$ și $v$, cu semnificația că există o muchie între nodurile $u$ și $v$.

Date de ieșire

Pe prima linie programul trebuie să afișeze costul minim de selecție care se poate obține. Pe a doua linie, programul trebuie să afișeze $K$ numere, reprezentând nodurile din selecție. În cazul în care există mai multe selecții care obțin acest cost, se poate afișa oricare dintre ele.

Restricții și precizări

• $1 \leq N \leq 10^6$
• $0 \leq K \leq N$
• $0 \leq v_i \leq 10^9$
• În cazul în care, după selectarea nodurilor nu mai există nicio componentă conexă, se consideră costul selecției ca fiind $0$.
• Pentru teste în valoare de $16$ puncte, $N \leq 10$.
• Pentru alte teste în valoare de $36$ puncte, $N \leq 1\ 000$.
• În cazul în care, costul corect este afișat, dar selecția afișată nu obține acest cost, se va acorda $50 \%$ din punctajul pe testul respectiv.

Exemplul 1

arborele_frumos.in

10 5
98 81 0 16 82 86 14 16 25 43
2 1
3 2
4 1
5 3
6 5
7 4
8 5
9 6
10 2

arborele_frumos.out

30
6 5 10 2 1

Explicație

În primul exemplu, o selecție de cost minim este cea formată din nodurile $1$, $2$, $5$, $6$, $10$. După ștergerea lor, rămân următoarele componente conexe:

• componenta formată din nodurile $4$ și $7$, cu costul $30$;
• componenta formată din nodul $3$, cu costul $0$;
• componenta formată din nodul $8$, cu costul $16$;
• componenta formată din nodul $9$, cu costul $25$.

Maximul dintre costuri este $30$.

Exemplul 2

arborele_frumos.in

10 0
77 21 22 64 90 29 62 34 25 24
2 1
3 1
4 1
5 4
6 2
7 4
8 2
9 5
10 2

arborele_frumos.out

448

Explicație

În al doilea exemplu, $K = 0$, așadar nu vom selecta niciun nod. Costul selecției devine egal cu suma coeficienților de frumusețe din arbore, adică $448$.