Fişierul intrare/ieşire:	colier.in, colier.out	Sursă	Algoritmiada 2009, Runda 2
Autor	Cosmin Gheorghe	Adăugată de	Gheorghe Cosmin •gcosmin
Timp execuţie pe test	0.1 sec	Limită de memorie	4736 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Colier

Catrinel are un colier cu N perle magice ce pot avea doua culori (rosu sau negru). Catrinel isi iubeste mult colierul, dar ei ii place si diversitatea, asa ca ea isi poate schimba colierul folosind urmatoarea operatie: alege o perla neagra, schimba culorile perlelor vecine (colierul este circular iar o perla poate avea cel mult doi vecini; vecinul din stanga si cel din dreapta) in culoarea opusa (din rosu in negru si invers) si elimina perla neagra aleasa din colier. Curioasa din fire Catrinel se intreaba daca folosind operatia descrisa mai sus poate sa elimine toate perlele din colier.

Date de intrare

Prima linie a fisierului de intrare colier.in contine T numarul de teste. Urmatoarele T linii vor contine descrierea testelor. Linia i + 1 contine numarul natural N reprezentand numarul perlelor din colier si descrierea colierului printr-un sir de 1 si 0, reprezentand culorile negru si respectiv rosu, nedespartit prin spatii.

Date de ieşire

Fisierul colier.out va contine T linii, fiecare continand "DA" sau "NU" (fara ghilimiele), daca exista un sir de operatii astfel incat Catrinel sa poata sa elimine toate perlele din colier sau nu.

Restricţii si precizari

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 10⁵
• Pentru teste in valoare de 20 de puncte se garanteaza ca N ≤ 20
• Pentru teste in valoare de 50 de puncte se garanteaza ca N ≤ 1000
• O perla dintr-un colier cu o singura perla nu are niciun vecin
• O perla dintr-un colier cu doua perle are un singur vecin
• O perla dintr-un colier cu mai mult de doua perle are doi vecini

Exemplu

Explicaţie

Pentru testul 5 operatiile vor arata asa : 0 1 1 -> 1 0 -> 1 -> colier vid (valorile ingrosate reprezinta perla neagra aleasa pentru operatie)

Cum se trimit solutii?