==Include(page="template/taskheader" task_id="itree")==
 
==Include(page="template/raw")==
 
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.
 
h2. Cerinta
 
Dandu-se un arbore, decideti daca acesta este arbore de intervale.
 
h2. 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.
 
h2. 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.
 
h2. 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
 

==Include(page="template/taskheader" task_id="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.
 
h2. Cerinta
 
Dandu-se un arbore, decideti daca acesta este arbore de intervale.
 
h2. Date de Intrare
 
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$}.
 
h2. Date de Iesire
 
Fisierul $itree.out$ 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.
 
h2. Restrictii
 
* $1 ≤ N ≤ 100.000$
 
h2. Exemplu
 
table(example). |_. itree.in |_. itree.out |
| 3
3
1 2
2 3
1
4
1 2
1 3
3 4
| YES
YES
YES |
 
 
==Include(page="template/taskfooter" task_id="itree")==

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

1320