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

Vezi solutiile trimise | Statistici

Arbore de cicluri

Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii.

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.

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.

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.

Restrictii

S 1 <= T <= 10

S 1 <= N <= 100.000

S 1 <= M <= 200.000

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

Cum se trimit solutii?