arbciclu

Arbore de cicluri

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

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

Poveste ...

==Include(page="template/raw")==

h2. Cerinta

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).

h2. Restrictii

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. Date de intrare

h2. Restrictii

...

S 1 <= T <= 10

h2. Date de iesire

S 1 <= N <= 100.000

...

S 1 <= M <= 200.000

h2. Exemplu

| arbciclu.in | arbciclu.out |
| linia1
linia2
linia3
| linia1
linia2
|

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") ==
 

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