colier

Colier

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

Poveste şi cerinţă...

Clarisa are un colier cu $N$ perle magice ce pot avea doua culori (rosu sau negru). Clarisa 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 Clarisa se intreaba daca prin operatia descrisa mai sus poate sa elimine toate perlele din colier.

h2. Date de intrare

Fişierul de intrare $colier.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $colier.out$ ...

Fisierul $colier.out$ va contine $T$ linii, fiecare continand $"DA"$ sau $"NU"$ (fara ghilimiele), daca Clarisa poate elimina toate perlele din colierul ei sau nu.

h2. Restricţii

h2. Restricţii si precizari
 
* $1 ≤ T ≤ 10$
* $1 ≤ N ≤ 10^5^$
* Pentru $20%$ din teste se garanteaza ca $N ≤ 20$
* Pentru alte $30%$ din teste 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

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. colier.in |_. colier.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6
1 1
1 0
2 10
2 11
3 011
4 1001
| DA
NU
DA
NU
DA
NU

|
h3. 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)

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