ro

In Romania exista N orase interconectate prin M autostrazi. O autostrada leaga exact 2 orase (de exemplu, autostrazile Bucuresti-Pitesti sau Bucuresti-Constanta). Toate autostrazile sunt deschise circulatiei in ambele sensuri si se poate ajunge din orice oras in orice alt oras folosind autostrazile existente. In urma aderarii la Uniunea Europeana, guvernul va trebui sa ia masuri pentru a respecta regulile europene referitoare la infrastructura rutiera. Aceste reguli mentioneza ca cel putin unul din cele 2 orase intre care exista o autostrada trebuie sa aiba rangul de capitala europeana. Initial, nici unul dintre cele N orase nu are rangul de capitala europeana si pentru fiecare din ele se cunoaste suma necesara (in milioane de euro) pentru a fi modernizat si promovat la rangul respectiv.
Intrucat fondurile guvernului sunt limitate, determinati care este suma totala minima pe care va trebui sa o cheltuiasca guvernul cu promovarea unor orase la rangurile de capitale europene in asa fel incat sa fie respectate regulile europene referitoare la infrastructura rutiera.
Pentru a rezolva aceasta problema aveti la dispozitie o informatie suplimentara din partea guvernului, si anume: oricum am alege o submultime de 14 orase dintre cele N, exista in aceasta submultime cel putin o pereche de orase A si B cu proprietatea ca exista un oras C diferit de A si B (nu neaparat din submultimea aleasa) astfel incat, daca s-ar inchide circulatia in ambele sensuri pe toate autostrazile care au o extremitate in C, atunci nu va mai exista nici un drum intre orasele A si B folosind autostrazile ramase deschise circulatiei. Aceasta conditie poate fi reformulata astfel: Daca privim infrastructura rutiera a Romaniei ca un graf neorientat conex cu N noduri si M muchii, orice componenta biconexa a acestui graf contine cel mult 13 noduri.

Date de intrare

Fisierul de intrare ro.in contine pe prima linie numerele intregi N, M separate printr-un spatiu, reprezentand numarul de orase si numarul de autostrazi. Urmatoarea linie contine N numere intregi S_i, separate prin cate un spatiu, reprezentand sumele necesare promovarii fiecarui oras i (de la 1 la N) la rangul de capitala europeana. Urmatoarele M linii contin cate 2 numere intregi distincte separate printr-un spatiu, U si V, avand semnificatia ca exista o autostrada intre orasul U si orasul V.

Date de iesire

Fisierul de iesire ro.out va contine pe prima linie suma minima pe care trebuie sa o plateasca guvernul pentru a respecta regulile europene referitoare la infrastructura rutiera. Pe a doua linie veti afisa numarul O, reprezentand numarul de orase promovate la rangul de capitala europeana. A treia linie a fisierului va contine O numere intregi distincte intre 1 si N, separate prin cate un spatiu, reprezentand orasele care au fost alese pentru a fi promovate la rangul de capitala europeana.

Restrictii si precizari

• 1<=N<=2007
• N-1<=M<=10000
• 1<=S_i<=1000000
• Orasele sunt numerotate cu numere intregi de la 1 la N.
• Intre 2 orase diferite va exista cel mult o autostrada.
• Cel putin 20% din fisierele de test vor avea M=N-1.
• Orasele alese pentru a fi promovate la rangul de capitala europeana pot fi afisate in orice ordine.
  

Timp maxim de executie/test: 1.3 secunde
Memorie totala disponibila 30 MB, din care 1 MB pentru stiva.

as. Mugurel Ionut Andreica
Universitatea Politehnica Bucuresti, Facultatea de Automatica si Calculatoare
mugurel_ionut@yahoo.com