Fişierul intrare/ieşire:arbciclu.in, arbciclu.outSursăHappy Coding 2006
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test3.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inarbciclu.out
2
3 3
1 2
1 3
3 2
4 5
1 2
1 3
3 2
4 3
2 4
YES
YES
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content