Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MWP3_1A1 - Manifestacja

Decyzja o rozwiązaniu Koła Naukowego Miłośników Algorytmów odbiła się szerokim echem w całym informatycznym świecie. Gdyby prowadzący zdawali sobie wcześniej sprawę z jej konsekwencji z pewnością nigdy by jej nie podjęli. Niestety jest już za późno! Oburzeni studenci postanowili walczyć o przywrócenie działalności KNMA. Po konsultacjach z górnikami, pielęgniarkami, nauczycielami i Al-Kaidą zapadła decyzja o zorganizowaniu manifestacji! Ta ostatnia grupa zaoferowała przy okazji darmowy pokaz fajerwerków. Demonstranci mają bardzo przebiegły plan. Zamierzają oni przejść z transparentami pod siedzibę uczelni, otoczyć ją i nie wypuścić z niej nikogo aż do momentu uzyskania pisemnego zapewnienia o wznowieniu działalności koła naukowego.

Niestety podczas organizacji manifestacji wystąpiły pewne problemy. Po pierwsze hasła umieszczone na transparentach okazały się za długie, dlatego też studenci byli zmuszeni je podzielić na pojedyncze wyrazy. Podział ten spowodował kolejne komplikacje. Utracona została kolejność wyrazów w hasłach. Na dodatek przygotowane transparenty pomieszały się z tymi nadesłanymi przez zaprzyjaźnione związki zawodowe. Organizatorzy muszą odtworzyć odpowiednią kolejność. Pamiętają oni, że ostatnia litera i-tego wyrazu pokrywała się z pierwszą literą wyrazu i+1-go, czasami jedynie różniły się one wielkością. Zasada pokrywania dotyczyła również wyrazu ostatniego i pierwszego w kolejności, dzięki czemu z transparentów można było utworzyć jeden okrąg. Ponieważ czasu jest mało demonstranci postanowili napisać program, który sprawdzi czy wykorzystując wszystkie transparenty da się ustawić je w opisanej wcześniej kolejności. Zgadnij kto napisze ten program? ;-)

Wejście

W pierwszej linii wejścia znajduje się jedna liczba naturalna Z (1 ≤ Z ≤ 1000) określająca ilość zestawów danych. W kolejnych liniach znajdują się zestawy danych.

W pierwszej linii każdego zestawu danych znajduje się jedna liczba naturalna n (1 ≤ n ≤ 1000) oznaczająca ilość transparentów z wyrazami. W kolejnych n liniach znajdują się wyrazy umieszczone na transparentach, po jednym w linii. Każdy wyraz składa z małych lub wielkich liter alfabetu angielskiego. Wyrazy mogą zawierać od 2 do 20 liter.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać "TAK" jeżeli możliwe jest przywrócenie odpowiedniej kolejności albo "NIE" w przeciwnym wypadku.

Przykład

Wejście:

2
4
INFORMATYKA
JESLI
WIECEJ
ALGORYTMOW
5
ALGORYTMOW
WIECEJ
JUZ
ZNAC
CHCEMY

Wyjście:

TAK
NIE

Dodane przez:Maciej Boniecki
Data dodania:2010-12-02
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
Pochodzenie:III Mistrzostwa WWSI w Programowaniu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.