== include(page="template/taskheader" task_id="soc2") ==

Poveste si cerinta...

Un grup de $N$ oameni de afaceri s-au antalnit cu ocazia unei conferinte. Unii dintre ei sunt dusmani, altii nu (de prietenie nu se prea pune problema cand este vorba de afaceri). Fiecare dintre ei are un cont in banca ce contine o anumita suma exprimata in euro. De fiecare data cand se intalnesc, se gandesc cum sa initieze o noua afacere. De data aceasta s-au decis sa infiinteze o societate, la care actionarii sa fie o parte dintre ei, astfel incat oricare doi oameni de afaceri care sunt actionari ai societatii sa nu fie dusmani, iar capitalul societatii (egal cu totalul sumelor din conturile actionarilor) sa fie maxim. Pentru a determina actionarii acestei societati, v-au angajat pe dumneavoastra si, daca le veti da raspunsul in timp util, veti fi recompensat cu o suma frumoasa.
Inainte de a va apuca de treaba, cei $N$ oameni de afaceri v-au pus la dispozitie informatii referitoare la conturile lor din banca si la relatiile de dusmanie dintre ei. Analizand problema, ati ajuns la concluzia ca relatiile de dusmanie pot fi reprezentate sub forma unui graf neorientat cu $N$ varfuri (corespunzatoare celor $N$ oameni de afaceri); intre doua varfuri diferite exista o muchie, daca cei doi oameni de afaceri corespunzatori celor doua varfuri din graf sunt dusmani (dusmania este reciproca). Graful are o structura speciala, mai exact el este un $graf cordal$. Un graf se numeste $graf cordal$ daca indeplineste una dintre urmatoarele $2$ conditii:
1.	Este un graf cu un singur nod.
2.	Se obtine inserand un nod nou $X$ într-un graf cordal $G$, astfel: se alege o submultime de noduri din $G$, cu proprietatea ca exista muchie intre oricare doua noduri din submultime (submultimea poate contine si doar un singur nod), si se introduce cate o muchie intre nodul nou inserat $X$ si fiecare nod din submultime.
 
 
O definitie echivalenta a grafurilor cordale este urmatoarea: un graf se numeste $graf cordal$ daca este conex si orice ciclu elementar (ce contine fiecare nod al grafului cel mult o data) avand cel putin 4 noduri contine cel putin o "coarda" (o muchie intre doua noduri care fac parte din ciclu, dar nu sunt adiacente pe ciclu).
In continuare, iata cateva exemple de grafuri cordale si grafuri care nu sunt cordale :
 

h2. Date de intrare