Arbore de cicluri

arbciclu

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

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

Un arbore de cicluri este un graf neorientat care are una din urmatoarele proprietati:

Poveste ...

* este un ciclu de lungime $K$ ({$K ≥ 3$})
* este un graf obtinut prin atasarea unui ciclu $C$ de lungime $K$ ({$K ≥ 3$}) la o muchie dintr-un arbore de cicluri $CT$

h2. Cerinta

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).
!problema/arbciclu?arbciclu.jpg!  
Dandu-se mai multe grafuri sa se determine pentru fiecare daca este un arbore de cicluri.

...

h2. Date de intrare

h2. Restrictii

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

h2. Date de intrare

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

h2. Date de iesire

* $1 ≤ T ≤ 10$
* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 200.000$

...

h2. Exemplu

table(example). |_. arbciclu.in |_. arbciclu.out |
|2
3 3
1 2
1 3
3 2
4 5
1 2
1 3
3 2
4 3
2 4
| YES
YES |

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

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

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

1323