Problem: Problem Statement

One day (call it day 0), you find a permutation $P$ of $N$ integers written on the blackboard in a single row. Fortunately you have another permutation $Q$ of $N$ integers, so you decide to play with these permutations.

Every morning of the day 1,2,3,... , you rewrite every number on the blackboard in such a way that erases the number $x$ and write the number $Q_x$ at the same position. Please find the minimum non-negative integer $d$ such that in the evening of the day $d$ the sequence on the blackboard is sorted in increasing order.

* * *

Input

The input consists of a single test case in the format below.

> $N$ $P_1$ $\ldots$ $P_N$ $Q_1$ $\ldots$ $Q_N$

The first line contains an integer $N$ ($1 \leq N \leq 200$). The second line contains $N$ integers $P_1,\ldots,P_N$ ($1 \leq P_i \leq N$) which represent the permutation $P$. The third line contains $N$ integers $Q_1,\ldots,Q_N$ ($1 \leq Q_i \leq N$) which represent the permutation $Q$.

Output

Print the minimum non-negative integer $d$ such that in the evening of the day $d$ the sequence on the blackboard is sorted in increasing order. If such $d$ does not exist, print -1 instead.

It is guaranteed that the answer does not exceed $10^{18}$.

Examples

Input| Output
---|---


6
2 3 1 4 5 6
3 1 2 5 4 6


|


4



6
1 2 3 4 5 6
3 1 2 5 4 6


|


0



6
2 3 1 4 5 6
3 4 5 6 1 2


|


-1






Example

Input




Output

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define REP(i,n) for (long long i=0;i<(n);i++)
#define FOR(i,a,b) for (long long i=(a);i<(b);i++)
#define dump(x)  cerr << #x << " => " << (x) << endl
#define MIN(vec) *min_element(vec.begin(), vec.end())
#define MAX(vec) *max_element(vec.begin(), vec.end())
#define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end()) //ソートの必要あり
#define IN(n,m)  (!(m.find(n) == m.end()))
#define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin())
#define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin())
#define EQ(a,b) (abs(a - b) < 1e-10)
using namespace std;
typedef long long LL;
constexpr int dx[4] = {0,1,0,-1};
constexpr int dy[4] = {1,0,-1,0};
constexpr long double pi = M_PI;
constexpr double eps = 1e-10;
// LONG_MAX,LLONG_MAX
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class Key,class Value> ostream& operator << (ostream &s, map<Key,Value> M)
{ for ( auto itr = begin(M); itr != end(M); ++itr) { s << itr->first << ":" << itr->second; } return s;}

inline long long mod(long long a, long long m) {
    return (a % m + m) % m;
}

// 拡張 Euclid の互除法
long long extGCD(long long a, long long b, long long &p, long long &q) {
    if (b == 0) { p = 1; q = 0; return a; }
    long long d = extGCD(b, a%b, q, p);
    q -= a/b * p;
    return d;
}

// 答えを x ≡ r (mod. M) として、{r, M} をリターン, 存在しない場合は {0, -1} をリターン
pair<long long, long long> ChineseRem(const vector<long long> &b, const vector<long long> &m) {
    long long r = 0, M = 1;
    for (int i = 0; i < (int)b.size(); ++i) {
        long long p, q;
        long long d = extGCD(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d)
        if ((b[i] - r) % d != 0) return make_pair(0, -1);
        long long tmp = (b[i] - r) / d * p % (m[i]/d);
        r += M * tmp;
        M *= m[i]/d;
    }
    return make_pair(mod(r, M), M);
}


int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> P(N);
    vector<int> Q(N);
    REP(i, N) {
        cin >> P[i];
        P[i]--;
    }
    REP(i, N) {
        cin >> Q[i];
        Q[i]--;
    }

    vector<int> group(N, -1);
    int g = 0;
    REP(i, N) {
        if (group[i] != (-1)) {
            continue;
        }
        int idx = i;
        while (true) {
            if (group[idx] != (-1)) break;
            group[idx] = g;
            idx = Q[idx];
        }
        g++;
    }
    vector<vector<int>> T(g);
    REP(i, N) {
        if (group[P[i]] != group[i]) {
            cout << -1 << endl;
            exit(0);
        }
        T[group[P[i]]].push_back(P[i]);
    }

    // 何ループ目かを求める.
    vector<long long> roop(g, 0LL);
    vector<long long> m(g, 0LL);
    REP(i, g) {
        vector<int> cur = T[i];
        m[i] = cur.size();
        int cnt = 0;
        while (true) {
            bool ok = true;
            REP(j, cur.size()-1) {
                if (cur[j+1] <= cur[j]) ok = false;
            }
            if (ok) {
                roop[i] = cnt;
                break;
            }
            bool turn = true;;
            REP(j, cur.size()) {
                cur[j] = Q[cur[j]];
                if (cur[j] != T[i][j]) {
                    turn = false;
                }
            }
            cnt++;
            if (turn) {
                cout << -1 << endl;
                exit(0);
            }
        }
    }
    pair<long long, long long> res = ChineseRem(roop, m);
    if (res.second == -1) cout << -1 << endl;
    else cout << res.first << endl;
    
}