Fişierul intrare/ieşire:	tgraf.in, tgraf.out	Sursă	.campion 2003
Autor	Mugurel Ionut Andreica	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.075 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Tgraf

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.

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.

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

• 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

Cum se trimit solutii?