Fişierul intrare/ieşire:	itree.in, itree.out	Sursă	Happy Coding 2006
Autor	Mugurel Ionut Andreica	Adăugată de
Timp execuţie pe test	0.35 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	3/5

Vezi solutiile trimise | Statistici

Itree

itree

Fie o multime de intervale pe axa OX. Consideram ca doua intervale se intersecteaza daca si numai daca au mai mult de un punct in comun (de exemplu intervalele [1, 5] si [3, 10] se intersecteaza, dar [1, 2] si [2, 3] nu se intersecteaza). Graful asociat acestei multimi de intervale este graful in care se asociaza un nod fiecarui interval si o muchie intre nodurile corespunzatoare fiecarei perechi de intervale care se intersecteaza.

Un graf G se numeste graf de intervale daca exista cel putin o multime de intervale al caror graf asociat sa fie izomorf cu G.

Un arbore (graf orientat conex cu N varfuri si N - 1 muchii) se numeste arbore de intervale daca este in acelasi timp si graf de intervale.

Cerinta

Dandu-se un arbore, decideti daca acesta este arbore de intervale.

Date de Intrare (fisier: itree.in)

Fisierul itree.in va contine pe prima linie un intreg T reprezentand numarul de teste din fisier. In continuare sunt descrisi T arbori. Pentru fiecare arbore pe prima linie se va afla un numar N - numarul de noduri ale arborelui. Urmatoarele N - 1 linii contin cate o pereche de numere A B, cu semnificatia ca exista o muchie intre nodurile A si B.

Date de Iesire (fisier: itree.out)

Fisierul itree va contine pe T linii. Pentru fiecare arbore din fisierul de intrare se va afisa "YES" daca acesta este arbore de intervale, respectiv "NO" in caz contrar.

Restrictii

S 1 <= N <= 100 000

itree.in itree.out
3 YES

3 YES

1 2 YES

2 3

1

4

1 2

1 3

3 4

Cum se trimit solutii?