Se dă un graf neorientat cu N noduri şi M muchii. Nodurile grafului sunt numerotate cu numere naturale de la 1 la N, iar fiecare nod i are asociat o valoare ai. Fiecare muchie [x, y] a grafului are costul egal cu min{ai | min(x, y) ≤ i ≤ max(x, y)}.
Cerinţă
Scrieţi un program care să determine nodurile unei componente conexe care conţine o muchie de cost maxim. Dacă există mai multe astfel de componente conexe, se cere să se determine componenta conexă care are o muchie de cost maxim incidentă cu un nod cu indice minim.
Date de intrare
Fişierul de intrare wg.in conţine pe prima linie numărul natural N. Pe următoarele N linii sunt date în ordine numerele naturale ai, 1 ≤ i ≤ N. Pe următoarea linie se află numărul natural M. Pe următoarele M linii se află câte două numere naturale x şi y, separate prin spaţiu, reprezentând faptul că există în graf o muchie între nodurile x şi y.
Date de ieşire
Fişierul de ieşire wg.out va conţine pe prima linie costul muchiei de cost maxim în componenta conexă căutată. Pe următoarea linie se va afişa numărul de vârfuri ale componentei conexe şi pe următoarele linii vârfurile componentei conexe în ordine crescătoare, câte unul pe linie.
Restricţii
1 ≤ N ≤ 100.000, 1 ≤ M ≤ 500.000, 0 ≤ ai ≤ 1.000.000.000,
Nu există muchii de la un nod la el însuşi,
Între două noduri există cel mult o muchie.