8. Yvettin Ementál Neschopnosti

Yvette sa na klávesnici pokazil medzerník. Hneď o tom aj napísala svojej kamarátke Xénii. Samozrejme, v rámci dobrých zvykov, bez diakritiky, interpunkcie a veľkých písmen:

ahojxenianeuverisalepokazilsamimedzernik

Lúštenie tejto správy Xénii chvíľku trvalo, no celkom sa jej to zapáčilo. Odpísala teda:

jeeejtojesrandapodmesipisatbezmedzier

Yvette lúštenie správy spočiatku veľmi nešlo. “To je nad moje mentálne schopnosti,” pomyslela si. Nakoniec však správu rozlúštila, a keďže nechcela Xéniu sklamať, odpovedala:

takdobrelendufamzetonebudenadmojementalneschopnosti

Táto správa Xéniu úprimne zmiatla. “Nad môj Ementál Neschopnosti? Čo to je? Už som počula o Prsteni Neviditeľnosti, Opasku Sily, aj Papučiach Obratnosti, ale o Ementáli Neschopnosti som ešte nepočula.”

Po chvíli zmätku a dvoch telefonátoch dievčatá pochopili, že ak si budú písať bez medzier, občas sa nejaká správa bude dať rozdeliť na slová viacerými spôsobmi. Preto sa rozhodli, že pri písaní budú používať iba obmedzenú množinu slov, tak, aby sa im toto nemohlo stať. Ako však zistiť, či je nejaká množina slov dobrá?

Úloha

Majme zoznam \(k\) rôznych slov. Dve rôzne postupnosti slov zo zoznamu budeme volať dvojičky, ak zreťazením slov z jednej postupnosti vznikne rovnaký reťazec ako zreťazením slov druhej postupnosti. Napríklad, ak by náš zoznam obsahoval slová {emental, mentalne, moj, moje, neschopnosti, schopnosti}, postupnosti (moje, mentalne, schopnosti) a (moj, emental, neschopnosti) sú dvojičky. Slová sa môžu v rámci postupností aj opakovať, postupnosti však musia byť rôžne. Teda napríklad postupnosť (moje, mentalne, schopnosti, moje, moje) je dvojička s postupnosťou (moj, emental, neschopnosti, moje, moje), ale postupnosti (moj, moje) a (moj, moje) dvojičky nie sú, lebo nie sú rôzne.

Vašou úlohou bude pre zadaný zoznam slov rozhodnúť, či preň existujú nejaké dvojičky.

Formát vstupu

Aby sme vám sťažili náhodné hádanie správnych odpovedí, v jednom vstupnom súbore bude niekoľko zadaní úlohy.

V prvom riadku bude jedno celé číslo \(t\) (\(1 \leq t \leq 10\)) – počet zadaní, ktoré máte vyriešiť. Ďalej je na vstupe \(t\) zadaní, každé z nich má nasledujúci formát.

V prvom riadku zadania je jedno celé číslo \(k\) (\(1 \leq k \leq 200,000\)) – počet slov v zozname. Nasleduje \(k\) riadkov, každý z nich obsahuje jeden neprázdny reťazec tvorený malými písmenami anglickej abecedy (a-z) – jedno slovo zo zoznamu. Všetky tieto slová sú navzájom rôzne.

Súčet dĺžok všetkých slov vo vstupnom súbore (teda zo všetkých \(t\) zadaní dokopy) označme \(N\). Bude platiť \(N \leq 200,000\).

Formát výstupu

Pre každé zadanie zo vstupu vypíšte (v rovnakom poradí) jeden riadok. Ak pre zadaný zoznam slov existujú dvojičky, riadok nech obsahuje iba slovo ano, ak neexistujú, riadok nech obsahuje iba slovo nie.

Hodnotenie

Vaše programy budeme testovať na štyroch skupinách testovacích vstupov. Pre jednotlivé skupiny budú platiť nasledujúce obmedzenia:

Súčet dĺžok všetkých slov v jednom zadaní označme \(n\). Vo vašich riešeniach uvádzajte časovú zložitosť vášho algoritmu v závislosti od parametrov \(n\) (celková dĺžka slov v zozname) a \(k\) (počet slov v zozname), teda nie od parametrov \(t\) a \(N\).

Okrem toho uveďte aj odhad časovej zložitosti vášho algoritmu iba v závislosti od parametra \(n\). Ak by teda napríklad váš algoritmus bežal v čase \(O(n^2k^3)\), môžete uviesť, že beží v čase \(O(n^5)\) (keďže \(k \leq n\) na každom vstupe).

Príklad

Input:

3
6
emental
mentalne
moj
moje
neschopnosti
schopnosti
4
korespondencny
seminar
z
programovania
4
aaa
aaab
bc
caaa

Output:

ano
nie
ano

Najkratšie dvojičky v poslednom zadaní sú postupnosti (aaab, caaa) a (aaa, bc, aaa).