tgraf

tgraf

Un tgraf este un graf neorientat avand una dintre 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

Cerinta

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.

Date de intrare

Pe prima linie a fisierului 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.

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.

Restrictii si precizari

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⁹
In general, solutia nu este unica.

Exemplu

tgraf.in

tgraf.out

4
1 0

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

Timp maxim de executie/test: 0.1 secunde

Mugurel Ionut Andreica
student Universitatea "Politehnica" Bucuresti
Contact: mugurel_ionut at yahoo.com