카드 섞기

바이타자르(Bajtazar)는 아들 바이텍(Bajtek)에게 카드 한 벌을 선물했습니다. 이 카드 한 벌은 $1$번부터 $n$번까지 번호가 매겨진 $n$장의 카드로 이루어져 있습니다.

바이텍은 선물을 무척 좋아했습니다. 저녁 내내 방에 앉아 카드를 섞으며 놀았고, 어찌나 능숙해졌는지 매번 완전히 똑같은 방식으로 섞게 되었습니다. 즉, 한 번 섞을 때 위치 $k$($1 \le k \le n$)에 있던 카드는 항상 위치 $a_k$($1 \le a_k \le n$)로 옮겨집니다.

어느 순간 아빠가 방에 들어와 이제 잘 시간이라고 말했습니다. 바이텍은 자기 전에 카드를 제대로 섞는 방법을 한 번만 보여 달라고 졸랐습니다. 그러자 바이타자르는 위치 $k$에 있던 카드가 위치 $b_k$($1 \le k, b_k \le n$)로 가도록 카드를 섞었습니다.

바이텍은 아빠가 능숙하게 카드를 섞는 모습에 감탄했고, 자기도 그렇게 하고 싶었습니다. 하지만 아직 어려서 아빠처럼 섞지는 못합니다. 그래서 한 가지 생각을 떠올렸습니다. 자신이 섞는 방법을 여러 번 반복하면 마지막에는 아빠가 섞은 것과 같은 배열이 되지 않을까 하는 것이었습니다.

이제 소년은 그것이 과연 가능한지 궁금해서 잠들 수 없습니다. 그를 도와주세요!

다시 말해, 순열 $a$를 $1$보다 큰 어떤 횟수만큼 반복해서 적용하여 순열 $b$를 만들 수 있는지 판별하면 됩니다.

첫째 줄에 정수 $n$($2 \le n \le 10^6$)이 주어집니다. 둘째 줄과 셋째 줄에는 각각 순열 $a_1, \dots, a_n$과 $b_1, \dots, b_n$이 주어지며, 각 순열은 $1$부터 $n$까지의 서로 다른 정수 $n$개로 이루어진 수열입니다. 두 순열은 서로 다르다고 가정해도 됩니다.

바이텍의 섞기를 $k$번 반복하면 바이타자르의 섞기와 정확히 같아지는 정수 $k > 1$이 존재하면 TAK를, 그렇지 않으면 NIE를 한 단어로 출력합니다. (TAK와 NIE는 각각 폴란드어로 "예"와 "아니요"를 뜻합니다.)