Tasowanie

Limit pamięci: 128 MB

Bajtazar dał w prezencie swojemu synowi, Bajtkowi, talię kart. Talia składa się z kart, ponumerowanych liczbami od 1 do .

Bajtek bardzo ucieszył się z prezentu. Przez cały wieczór siedział w swoim pokoju i bawił się, tasując karty w talii. Doszedł przy tym do takiej wprawy, że za każdym razem wychodziło mu to tak samo, tzn. podczas tasowania karta z pozycji (dla ) przechodziła zawsze na pozycję (oczywiście ).

W pewnym momencie do pokoju Bajtka przyszedł tata i powiedział, że czas już spać. Bajtek uprosił tatę, aby pokazał mu jeszcze przed snem, jak powinno się tasować karty. Wówczas Bajtazar potasował karty tak, że karta z pozycji znalazła się na pozycji (znów ).

Bajtek patrzył z podziwem na to, z jaką wprawą jego tata tasuje karty. Sam też chciałby tak umieć! Niestety Bajtek jest jeszcze mały i nie umie tasować tak jak jego tata. Wpadł jednak na pomysł, że spróbuje kilka razy powtórzyć swój sposób tasowania, tak aby na końcu otrzymać taki układ, jak po tasowaniu taty.

Teraz chłopiec nie może zasnąć, bo zastanawia się, czy jest to w ogóle możliwe. Pomóż mu!

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (). Drugi i trzeci wiersz zawierają opisy permutacji oraz , czyli ciągi parami różnych liczb całkowitych z zakresu od 1 do . Możesz założyć, że te dwie permutacje są różne.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedno słowo TAK lub NIE, w zależności od tego, czy istnieje takie , że powtarzając -krotnie tasowanie Bajtka, można uzyskać potasowanie Bajtazara.

Przykład

Dla danych wejściowych:

4
2 4 3 1
1 2 3 4

poprawną odpowiedzią jest:

TAK

natomiast dla danych:

4
1 2 3 4
2 4 3 1

poprawną odpowiedzią jest:

NIE

Autor zadania: Jakub Łącki.