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>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000

#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())


int p[205],q[205];
int n;
struct s{
    int par[205];
    void init(){ rep(i,205) par[i] = i;}
    int find(int x){ if(x == par[x]) return x; else return par[x] = find(par[x]);}
    void unite(int x,int y){
        x = find(x); y = find(y);
        if(x == y) return;
        par[x] = y;
    }
    bool same(int x,int y){ return find(x) == find(y); }
}kaede;
vector<int>id[205];
template<class T> T extgcd(T a, T b, T& x, T& y) { for (T u = y = 1, v = x = 0; a;) { T q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; }
template<class T> T mod_inv(T a, T m) { T x, y; extgcd(a, m, x, y); return (m + x % m) % m; }
ll mod_pow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }


ll garner(vector<P> mr, ll mod){
    mr.emplace_back(mod, 0);

    vector<ll> coffs(sz(mr), 1);
    vector<ll> constants(sz(mr), 0);
    FOR(i, sz(mr) - 1){
        // coffs[i] * v + constants[i] == mr[i].second (mod mr[i].first) を解く
        ll v = (mr[i].second - constants[i]) * mod_inv<ll>(coffs[i], mr[i].first) % mr[i].first;
        if (v < 0) v += mr[i].first;

        for (int j = i + 1; j < sz(mr); j++) {
            (constants[j] += coffs[j] * v) %= mr[j].first;
            (coffs[j] *= mr[i].first) %= mr[j].first;
        }
    }

    return constants[sz(mr) - 1];
}
ll gcd(ll a, ll b){
    if(a<b)swap(a,b);
    if(b==0) return a;
    else return gcd(b,a%b);
}
ll preGarner(vector <ll> &b, vector <ll> &m, ll MOD) {
    for (int i = 0; i < b.size(); i++) {
        for (int j = 0; j < i; j++) {
            ll g = gcd(m[i], m[j]);
            if ((b[i] - b[j]) % g != 0) return -1;

            m[i] /= g, m[j] /= g;
            ll gi = gcd(m[i], g), gj = g / gi;
            do {
                g = gcd(gi, gj);
                gi *= g, gj /= g;
            } while (g != 1);
            m[i] *= gi, m[j] *= gj;
            b[i] %= m[i], b[j] %= m[j];
        }
    }

    ll res = 1;
    for (int i = 0; i < b.size(); i++) (res *= m[i]) %= MOD;
    return res;
}

int las[205];
vector<int>pos[205];
signed main(){
    cin >> n;
    repn(i,n) cin >> p[i];
    kaede.init();
    repn(i,n) {cin >> q[i];kaede.unite(i,q[i]);}

    repn(i,n){
        id[kaede.find(p[i])].pb(p[i]);
        pos[kaede.find(p[i])].pb(i);
    }
    vector<pair<int,int>>vec;
    repn(i,n){
        if(id[i].empty()) continue;
        rep(j,205){
            rep(x,id[i].size()) if(x && id[i][x-1] > id[i][x]) goto fail;
            vec.pb(mp(id[i].size(),j)); goto nxt; fail:;
            rep(x,id[i].size()) id[i][x] = q[id[i][x]];
        }
        puts("-1"); return 0; nxt:;
        rep(s,pos[i].size()) las[pos[i][s]] = id[i][s];
    }
    repn(i,n) assert(las[i]);
    repn(i,n) if(las[i] != i) {  puts("-1"); return 0;  }
    vector<ll>v1,v2; rep(i,vec.size()) { v1.pb(vec[i].fi); v2.pb(vec[i].sc); }
    ll l = preGarner(v2,v1,2000000000000000009LL);
    if(l == -1) { puts("-1"); return 0;}
    rep(i,vec.size()) { vec[i].fi = v1[i]; vec[i].sc = v2[i]; }
    ll x =  garner(vec,2000000000000000009LL);
    cout << x << endl;
}