Arbore de cicluri

arbciclu

==Include(page="template/taskheader" task_id="arbciclu")==

== include(page="template/taskheader" task_id="arbciclu") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| arbciclu.in | arbciclu.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="arbciclu") ==

==Include(page="template/raw")==
 
Arbore de cicluri
 
 
 
Un arbore de cicluri este un graf neorientat care are una din urmatoarele proprietati:
 
1) este un ciclu de lungime K (K >= 3)
 
2) este un graf obtinut prin atasarea unui ciclu C de lungime K (K >= 3) la o muchie dintr-un arbore de cicluri CT
 
Atasarea unui ciclu la o muchie dintr-un graf inseamna inlocuirea unei muchii din ciclu cu o muchie din graf (si de asemenea inlocuirea celor doua noduri ale muchiei din ciclu cu cele doua noduri ale muchiei din graf).
 
Dandu-se mai multe grafuri sa se determine pentru fiecare daca este un arbore de cicluri.
 
h2. Date de Intrare
 
Prima linie a fisierului de intrare arbciclu.in contine un numar natural T, reprezentand numarul de grafuri care se dau. Pentru fiecare graf dat, prima linie va contine doua numere naturale: N si M. N este numarul de noduri din graf si M este numarul de muchii. Urmatoarele M linii vor contine cate doua numere intregi A si B, cu semnificatia ca exista o muchie intre nodul A si nodul B. Nodurile din graf sunt numerotate cu numere de la 1 la N.
 
h2. Date de Iesire
 
Pentru fiecare graf, in ordinea data in fisierul de intrare, se va afisa in fisierul arbciclu.out sirul "YES" daca graful este un arbore de cicluri, sau "NO" in caz contrar.
 
h2. Restrictii
 
S 1 <= T <= 10
 
S 1 <= N <= 100.000
 
S 1 <= M <= 200.000
 
h2. Exemplu
 
arbciclu.in arbciclu.out
2 YES
 
3 3 YES
 
1 2
 
1 3
 
3 2
 
4 5
 
1 2
 
1 3
 
3 2
 
4 3
 
2 4
 
 
==Include(page="template/taskfooter" task_id="arbciclu")==