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

FR_01_M5 - Trzyliterówka

Trzyliterówka

Jasiu wymyślił nową łamigłówkę. Mając wyrazy trzyliterowe, należy wszystkie połączyć tak, aby pierwsza litera wyrazu następnego była ostatnią literą wyrazu poprzedzającego. Mając trzy wyrazy: tik tak kot, można je dopasować np. tak: tikotak, co prowadzi do rozwiązania łamigłówki.
Zaczął więc Jasiu tworzyć zestawy haseł, gdy pomyślał, że szybciej będzie generować je programem. Napisał więc program i zauważył, że losowe hasła często nie rozwiązują łamigłówki, a tak być nie może. Napisał nowy program, który wyłonić miał spośród wygenerowanych zestawów te poprawne. No tak, miał, bo program do dzisiaj nie zakończył działania. Pomóż Jasiowi i napisz program, który wskaże zestawy haseł prowadzące do rozwiązania trzyliterówki.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę zestawów danych. Każdy zestaw danych opisany jest w dwóch wierszach. W pierwszym podana jest liczba całkowita n (1 ≤ n ≤ 100000) określająca liczbę haseł. W wierszu drugim podanych jest n trzyliterowych haseł złożonych z małych liter alfabetu łacińskiego.

Wyjście
Dla każdego zestawu danych należy wypisać albo słowo TAK, jeśli istnieje co najmniej jeden sposób prowadzący do rozwiązania łamigłówki, albo słowo NIE, jeśli nie jest to możliwe.

 

Przykład

Wejście
3
2
ten kot
3
tik tak kot
4
kto kot kat tok

Wyjście
TAK
TAK
NIE


Dodane przez:Mariusz Śliwiński
Data dodania:2014-05-07
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
Pochodzenie:FRAKTAL
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.