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.