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 |
Vezi solutiile trimise | Statistici
Arbore de cicluri
Un arbore de cicluri este un graf neorientat care are una din urmatoarele proprietati:
- 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
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
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 100.000
- 1 ≤ M ≤ 200.000
Exemplu
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 |