POLSKI SPOJ

Ostatnia sprawność należy do kategorii specjalistycznych związanych z profilem zastępu i nazywa się "Filogen". Celem sprawdzianu jest weryfikacja umiejętności porównywania historii ewolucji (np. mrówek, którymi interesuje się Jaś) na podstawie wyznaczonych eksperymentalnie drzew filogenetycznych, ukazujących możliwą historię ewolucji (np. od organizmów jednokomórkowych do mrówek). W drzewie binarnym możemy wyróżnić węzły bez potomków (liście), węzły pośrednie (mające jednego rodzica i dokładnie dwóch potomków) oraz korzeń drzewa, który nie ma rodzica, ale ma dwóch potomków. Drzewem filogenetycznym nazywać będziemy dowolne drzewo binarne ze zbiorem liści ponumerowanych od 1 do n (2 <= n <= 10000). Drzewa filogenetyczne będziemy przedstawiać w następujący sposób: z każdym liściem a stowarzyszymy listę jednoelementową La = a; jeżeli dwa liście a oraz b mają wspólnego sąsiada, to stowarzyszymy z nim listę (a b). Niech x i y będą dwoma węzłami w drzewie mającymi wspólnego rodzica oraz załóżmy, że odpowiadają im listy Lx oraz Ly. Wtedy dla ich rodzica tworzymy listę (Lx Ly) (występuje dokładnie jedna spacja pomiędzy listami).

• zestawy testowe 1-5 [każdy za 2 punkty, limit czasu 1 s]: n <= 1000,
• zestawy testowe 6-10 [każdy za 2 punkty, limit czasu 5 s]: n <= 10000.

Wejście

W pierwszej linii podana została liczba testów t (t <= 100), z których składa się dany zestaw testowy. Następnie każdemu testowi odpowiadają trzy kolejne linie. W pierwszej linii podana została liczba liści n. W drugiej linii podano pierwszą listę, natomiast w trzeciej linii podano drugą listę.

Wyjście

Na wyjściu, dla kolejnych testów w oddzielnych liniach, należy wypisać słowo TAK lub NIE jako odpowiedź na pytanie: czy podane listy opisują to samo drzewo.

Przykład (jednego zestawu testowego)

Wejście:
2
5
(((1 2) 5) (3 4))
((4 3) ((2 1) 5))
3
(1 (2 3))
((1 2) 3)

Wyjście:
TAK
NIE