Wędrowni treserzy pcheł

Limit pamięci: 32 MB

W Bajtocji można spotkać wędrownych treserów pcheł. Tresowane pchły uczone są tańca, polegającego na wykonywaniu precyzyjnych skoków w rytm muzyki. Dokładnie wygląda to tak: treser układa na stole w rządku ponumerowane żetony, przy czym żetony nie muszą być ułożone po kolei. Na każdym żetonie, oprócz jego numeru, jest również napisany numer żetonu, na który powinna z niego skoczyć pchła. Następnie treser ustawia po jednej pchle na każdym z żetonów i włącza muzykę. Na początku każdego taktu, każda z pcheł wykonuje skok wprost na żeton, którego numer jest napisany na żetonie, na którym w danej chwili stoi. W trakcie tańca może się zdarzyć, że kilka pcheł znajdzie się na tym samym żetonie i razem wykonują dalsze skoki.

Załóżmy, że mamy tresowanych pcheł i żetonów. Jeśli podamy, jakie liczby znajdują się kolejno na żetonach numer , to jednoznacznie opiszemy układ choreograficzny, jaki zaprezentują pchły. Jednak może się okazać, że dwa różne zestawy żetonów dają ten sam układ, jeśli tylko odpowiednio je ułożymy.

Przykład

Powiedzmy, że mamy trzy żetony. Jeśli z żetonu nr 1 należy skoczyć na żeton nr 2, z żetonu nr 2 na żeton nr 3, a z żetonu nr 3 na żeton nr 1 (w skrócie: ), to pchły będą tańczyć "w kółko" i żadne dwie nigdy się nie spotkają na tym samym żetonie. Jest to inny układ tańca, niż np. , gdzie już po dwóch taktach wszystkie trzy pchły spotkają się na żetonie nr 3 i dalej będą razem skakać w miejscu.

Natomiast układy oraz są takie same - wystarczy ułożyć żetony na stole w rzędzie, w pierwszym przypadku w kolejności od lewej do prawej, a w drugim od prawej do lewej, a pchły odtańczą ten sam taniec.

Zadanie

Gawiedź bardzo się niecierpliwi, gdy pchły tańczą według tego samego układu więcej niż raz. Dlatego potrzebny jest program, który:

• wczyta ze standardowego wejścia liczbę przypadków testowych,
• dla każdego z przypadków wczyta ze standardowego wejścia opis dwóch zestawów żetonów i rozstrzygnie, czy żetony z tych zestawów można ułożyć na stole tak, by pchły wykonały taki sam taniec,
• wypisze odpowiedzi na standardowe wyjście.

Wejście

W pierwszym wierszu pliku tekstowego standardowego wejścia znajduje się jedna liczba całkowita równa liczbie przypadków testowych, .

Kolejne wiersze standardowego wejścia opisują kolejne przypadki testowe - każdy przypadek zajmuje trzy kolejne wiersze pliku. Pierwszy z nich zawiera jedną liczbę całkowitą , równą liczbie żetonów. Każdy z dwóch następnych wierszy zawiera opis zestawu żetonów w postaci ciągu liczb całkowitych z przedziału , pooddzielanych pojedynczymi odstępami; -ty wyraz ciągu oznacza numer żetonu, na który mają skakać pchły z żetonu nr .

Wyjście

Dla każdego z przypadków testowych ze standardowego wejścia należy wypisać na standardowe wyjście dokładnie jeden wiersz, zawierający dokładnie jedną literę:

• "T" - jeśli oba zestawy żetonów można ułożyć tak, aby pchły wykonały taki sam taniec,
• "N" - w przeciwnym wypadku.

Przykład

Dla danych wejściowych:

2
3
2 3 1
2 3 3
4
2 3 2 4
1 3 2 3

poprawną odpowiedzią jest:

N
T

Autor zadania: Marcin Sawicki.