VIII Olimpiada Informatyczna 2000/2001
Zadanie: PCH
Autor: Marcin Sawicki
Wędrowni treserzy pcheł
Zawody III stopnia, dzień próbny 26 marzec 2001
Plik źródłowy: PCH.??? (np. pas, c, cpp)
Plik wykonywalny: PCH.exe
Plik wejściowy: PCH.in
Plik wyjściowy: PCH.out

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 n tresowanych pcheł i n żetonów. Jeśli podamy, jakie liczby znajdują się kolejno na żetonach numer 1,2,...,n, 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: 1->2, 2->3, 3->1), 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. 1->2, 2->3, 3->3, 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 1->2, 2->3, 3->2, 4->4 oraz 1->1, 2->3, 3->2, 4->3 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:

Wejście

W pierwszym wierszu pliku tekstowego pch.in znajduje się jedna liczba całkowita d równa liczbie przypadków testowych, 1<=d<=100.

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

Wyjście

Dla każdego z przypadków testowych z pliku pch.in należy wypisać do pliku tekstowego pch.out dokładnie jeden wiersz, zawierający dokładnie jedną literę:

Przykład

Dla pliku wejściowego pch.in: 
2
3
2 3 1
2 3 3
4
2 3 2 4
1 3 2 3
poprawną odpowiedzią jest plik wyjściowy pch.out 
N
T