Shuffling Cards

Bajtazar gave his son Bajtek a deck of cards as a present. The deck has $n$ cards, numbered from $1$ to $n$.

Bajtek loved the gift. He spent the whole evening in his room shuffling the deck, and he grew so practiced that every shuffle came out exactly the same way: during a shuffle the card at position $k$ (for $1 \le k \le n$) always moved to position $a_k$ (with $1 \le a_k \le n$).

At some point Bajtek's father came in and said it was time for bed. Bajtek begged him to show, one last time before sleep, how cards should really be shuffled. So Bajtazar shuffled them so that the card at position $k$ ended up at position $b_k$ (again $1 \le k, b_k \le n$).

Bajtek admired how skillfully his father shuffled and wished he could do the same. He is still little, though, and cannot shuffle the way his father does. But he had an idea: he will repeat his own shuffle several times, hoping that in the end the deck ends up in the same arrangement as after his father's shuffle.

Now the boy cannot fall asleep, wondering whether this is even possible. Help him!

In other words, decide whether the permutation $b$ can be obtained by applying the permutation $a$ some number of times greater than one.

The first line contains a single integer $n$ ($2 \le n \le 10^6$). The second and third lines describe the permutations $a_1, \dots, a_n$ and $b_1, \dots, b_n$: each is a sequence of $n$ pairwise distinct integers from $1$ to $n$. You may assume that the two permutations are different.

Print a single word: TAK if there exists an integer $k > 1$ such that repeating Bajtek's shuffle $k$ times produces exactly Bajtazar's shuffle, or NIE otherwise. (TAK and NIE are the Polish words for "yes" and "no".)