Slalom tra le telecamere

Alle Olimpiadi invernali è stata creata una struttura comprendente varie piste da fondo, tutte percorribili in entrambe le direzioni e raccordate tramite aree di snodo.
Da ogni snodo è possibile imboccare una o più piste, mentre ogni pista collega due snodi distinti disposti ai suoi due estremi (e la pista non contiene altri snodi al suo interno).
La struttura permette agli atleti di spostarsi da ogni snodo a ogni altro snodo muovendosi sempre su pista (ovvero, senza togliersi gli sci dai piedi).
Inoltre, il percorso da seguire per passare da un certo snodo a un qualunque altro snodo è unico per ogni coppia di snodi (in pratica, la struttura non contiene cicli).

I dirigenti della televisione devono valutare dove localizzare le postazioni fisse delle telecamere, da piazzare in alcuni degli snodi della struttura, in modo da poter riprendere tutte le gare.
Gli snodi vengono numerati da 1 a N, e la pista avente gli snodi i e j come estremi viene indicata tramite la coppia di interi i e j.

Nel valutare il costo delle postazioni fisse per le telecamere, i dirigenti hanno stimato il costo di installazione per ciascuno snodo (tali costi non sono necessariamente uguali e possono variare da snodo a snodo).
Inoltre, per ogni pista, almeno uno tra i due snodi che essa collega deve contenere una telecamera per garantire la copertura televisiva.

Aiutate i dirigenti a identificare gli snodi che danno luogo alla copertura televisiva di costo minimo, calcolato come la somma dei costi di installazione delle telecamere in tali snodi.

Dati in Input

• La prima riga del file input.txt contiene l’intero positivo N, il numero di snodi nella struttura.
• La riga successiva contiene N interi positivi separati da uno spazio per rappresentare, nell’ordine, i costi per l’installazione delle telecamere negli snodi 1, 2, ..., N.
• Le successive N-1 righe contengono coppie di interi positivi che rappresentano le piste. Ogni riga è composta da due interi distintii e j separati da uno spazio, a rappresentare la pista avente gli snodi i e j come estremi. Da notare che la stessa pista non può apparire in più di una riga e l’ordine dei due interi specificati per la pista non è significativo (sia la coppia i e j che la coppia j e irappresentano la medesima pista).

Dati in Output

Il file output.txt è composto da due righe.

• La prima riga contiene un intero positivo che rappresenta il numero P di snodi che garantiscono la copertura televisiva con il minimo costo (ossia, tali snodi minimizzano la somma dei costi di installazione delle telecamere).
• La seconda riga contiene P interi positivi separati da uno spazio per indicare quali sono gli snodi coinvolti in tale copertura.

Da notare che possono esistere più soluzioni valide e, in tal caso, è sufficiente restituirne una qualunque come risposta (come mostrato negli esempi).

Assunzioni

• 2 ≤ N ≤ 400000
• 1 ≤ P ≤ N

Esempi