==Include(page="template/taskheader" task_id="soc")==

Un grup de $N$ oameni de afaceri s-au intalnit cu ocazia unei conferinte. Unii dintre ei sunt prieteni, altii nu. Fiecare dintre ei are un cont 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 fie prieteni, 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.

Un grup de $N$ oameni de afaceri s-au intalnit cu ocazia unei conferinte. Unii dintre ei sunt prieteni, altii nu. Fiecare dintre ei are un cont bancar 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 fie prieteni, 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 prietenie dintre ei. Analizand problema, ati ajuns la concluzia ca relatiile de prietenie 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 prieteni (prietenia este reciproca). Graful are o structura speciala, mai exact el este un cograf. Un graf se numeste cograf daca indeplineste cel putin una dintre urmatoarele 3 conditii:

In fisierul $soc.out$ veti afisa, pe prima linie, capitalul maxim al societatii. Pe urmatoarea linie veti afisa numarul {$A$}, reprezentand numarul de actionari ai societatii. Pe cea de-a treia linie veti afisa numerele oamenilor de afaceri care vor fi actionari, separate prin cate un spatiu. Daca exista mai multe posibilitati de a alege actionarii societatii astfel incat capitalul acesteia sa fie maxim, puteti afisa oricare din ele.

h2. Restrictii si precizari:

h2. Restrictii si precizari

* $1 ≤ N ≤ 256$
* $0 ≤ M ≤ N*(N-1)/2$

3 4 5
|

==Include(page="template/taskfooter" task_id="soc")==

 
 
 
 
 
 
 
 
 
==Include(page="template/taskfooter" task_id="soc")==

467