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

Poveste si cerinta...

Un {*tgraf*} este un graf neorientat avand una din urmatoarele proprietati:
 
* are un singur varf
* contine un varf izolat (care nu este adiacent cu nici un alt varf), iar graful obtinut prin inlaturarea acestui varf este un {*tgraf*}
* contine un varf care este adiacent cu toate celelalte, iar graful obtinut prin inlaturarea acestui varf si a muchiilor adiacente este un {*tgraf*}
 
O definitie echivalenta a unui tgraf este urmatoarea: fiecarui nod $K$ i se poate atribui o valoare nenegativa $a[K]$, astfel incat sa existe un numar intreg strict pozitiv $T$, cu proprietatea ca orice submultime de varfuri din graf este {*independenta*} daca si numai daca suma valorilor asociate varfurilor din submultime este strict mai mica decat $T$. O submultime se numeste {*independenta*} daca este adevarata una din urmatoarele afirmatii:
 
* este formata dintr-un singur varf
* intre oricare doua varfuri care fac parte din submultime nu exista muchie
 
Dandu-se un tgraf, atribuiti fiecarui nod $K$ o valoare nenegativa $a[K]$ si determinati numarul $T$, astfel incat sa fie respectata definitia precizata mai sus.

h2. Date de intrare

...

Pe prima linie a fisierului de intrare $tgraf.in$ se afla un numar intreg $P$, reprezentand numarul de tgrafuri ce vor fi descrise in continuare. Un tgraf este descris pe mai multe linii, astfel:
 
* pe prima linie se afla numerele intregi $N$ si $M$, separate printr-un spatiu, reprezentand numarul de varfuri si numarul de muchii ale tgrafului
* pe urmatoarele $M$ linii se afla cate doua numere intregi distincte $a$ si $b$, din multimea ${1,2,..,N}$, avand semnificatia ca exista muchie intre varful numerotat cu $a$ si cel numerotat cu $b$
 
Descrierile a doua tgrafuri consecutive sunt separate printr-o linie goala.

h2. Date de iesire

...

Pentru fiecare din cele $P$ tgrafuri din fisierul de intrare va trebui sa afisati cate doua linii in fisierul $tgraf.out$ : prima linie va contine numarul $T$, iar a doua va contine $N$ numere intregi nenegative, reprezentand valorile asociate varfurilor, in ordine, de la $1$ la $N$.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ P ≤ 20$
* $1 ≤ N ≤ 25$
* $0 ≤ M ≤ N*(N-1)/2$
* Numarul determinat $T$ si valorile asociate varfurilor trebuie sa fie mai mici sau egale cu $10{^9^}$
* In general, solutia nu este unica.

h2. Exemplu
table(example). |_. tgraf.in |_. tgraf.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 4
1 0

h3. Explicatie

2 0

...

3 3
1 2
1 3
2 3
 
4 2
1 4
3 4
| 1
0
1000
10 20
2
1 1 1
8
2 1 4 6
|

== include(page="template/taskfooter" task_id="tgraf") ==