cho.sh

Card Shuffling

Given a permutation of card positions and a target assignment of each card to a player, find the minimum number of shuffles so every card reaches its target player, or -1.

Medium6ArrayMathImplementationNumber theoryInterviewNo attempts yetTime limit2sMemory limit128 MB

Problem

There are N cards whose initial positions are numbered from 0 to N-1. When the cards are dealt in their current order to players 0, 1, and 2, the card at position j goes to player j mod 3.

The card that was initially at position i must eventually be dealt to player P[i].

One shuffle method is given as a permutation S of length N. After one shuffle, the card currently at position i moves to position S[i].

Find the minimum number of shuffles needed to satisfy the target distribution.

Input

The first line contains N. N is a multiple of 3 and satisfies 3 <= N <= 48.

The second line contains the sequence P of length N. Each element of P is one of 0, 1, and 2.

The third line contains the sequence S of length N. Each element of S is an integer from 0 to N-1, and no value appears more than once.

Output

Print the minimum number of shuffles needed to satisfy the target distribution. If it can never be satisfied, print -1.