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

#define X first
#define Y second
#define eb emplace_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define EFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP rep
using vint=vector<int>;
typedef __int128 ll;
typedef ll LL;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> inline bool MX(T&l, const T&r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T&l, const T&r){return l>r?l=r,1:0;}

int N;
int when[214];
bool is_composite[414];
vector<int> primes;


//#define int long long

LL extgcd(LL a, LL b, LL &x, LL &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }

  LL ret = extgcd(b, a%b, x, y);
  LL nx = y;
  LL ny = x - a/b*y;
  x = nx;
  y = ny;
  return ret;
}

LL china2(const vector<LL> &a, const vector<LL> &m) {
  __int128 p=1;
  LL re=0, pp,x,y;
  rep(i, m.size()) {
    p *= m[i];
    if (p > 1000000000000000000) break;
  }
  rep(i, m.size()) {
    pp = p/m[i];
    extgcd(m[i], pp, x, y);
    (re+=pp*y%p*a[i]%p) %= p;
  }
  return (re%p+p)%p;
}

int updChina(map<LL,pll> &mp, LL a, LL m, LL p) {
  if (mp.count(p)) {
    pll tmp = mp[p];
    if ((tmp.X-a)%min(tmp.Y, m)) return 1;

    if (tmp.Y < m) mp[p] = pll(a, m);
  } else {
    mp[p] = pll(a, m);
  }
  return 0;
}

LL china(const vector<LL> &a, const vector<LL> &m) {
  map<LL, pll> mp;
  pll tmp;
  LL num, p=1;
  rep(i, a.size()) {
    num = m[i];
    rep(j, primes.size()) if (m[i]%primes[j]==0) {
      p = 1;
      while (num%primes[j] == 0) {
        p*=primes[j];
        num/=primes[j];
      }
      if (updChina(mp, a[i], p, primes[j])) return -1;
    }
    if (num > 1) if (updChina(mp, a[i], num, num)) return -1;
  }
  vector<LL> aa, mm;
  for (auto temp : mp) {
    num=temp.Y.X; p=temp.Y.Y;
    aa.pb((num%p+p)%p);
    mm.pb(p);
  }
  return china2(aa,mm);
}

vint Merge(vint &p, vint &q) {
  vint ret(N);
  rep(i, N) {
    ret[i] = q[p[i]];
  }
  return ret;
}

signed  main(){
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(20);

  reps(i, 2, 214) {
    if (is_composite[i]) continue;
    primes.eb(i);
    for (int j=i*i; j<214; j+=i) {
      is_composite[j] = true;
    }
  }

  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];
  }

  fill(when, when+N, -1);

  vint cur = P;
  vector<LL> a(N, -1);
  vector<LL> b(N, -1);
  rep(i, N*3) {
    rep(j, N) {
      if (cur[j] == j) {
        if (when[j] == -1) when[j] = i;
        else if (a[j] == -1) {
          a[j] = i-when[j];
          b[j] = when[j];
          assert(a[j] > b[j]);
        }
      }
    }

    cur = Merge(cur, Q);
  }

  long long ans = (long long) china(b, a);
  if (ans == -1) {
    cout << ans << endl; 
    return 0;
  }
  vint perm(N);
  rep(i, N) perm[i] = i;
  vint mul = Q;
  rep(i, 62) {
    if (ans >> i & 1) {
      perm = Merge(perm, mul);
    }
    mul = Merge(mul, mul);
  }
  auto test = Merge(perm, P);
  rep(i, N) {
    if (test[i] != i) {
      cout << "-1\n";
      return 0;
    }
  }
  
  cout << ans << endl;
}