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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 2010

// {a, {b, c}} : a = gcd(p, q) = bp + cq
pair<ll,pair<ll,ll>> ext_gcd(ll p, ll q) {
  if (q == 0) return {p, {1, 0}};
  auto r = ext_gcd(q, p%q);
  return {r.first, {r.second.second, r.second.first - p/q*r.second.second}};
}


/* 中国剰余定理 */

pair<ll,ll> CRT(ll a1, ll m1, ll a2, ll m2){
  auto eg = ext_gcd(m1, m2);
  ll d = eg.first;
  if((a2 - a1) % d) return {0, -1};
  ll m = m1 / d * m2;
  ll r = ((a1 + m1 * ((__int128_t)(a2 - a1) / d * eg.second.first % (m2/d))) % m + m) % m;
  return {r, m};
}


int main(){
  int N, p[SIZE], q[SIZE], revp[SIZE];
  bool used[SIZE] = {};

  scanf("%d", &N);

  for(int i=0; i<N; i++) { scanf("%d", p+i); p[i]--; revp[p[i]] = i;}
  for(int i=0; i<N; i++) { scanf("%d", q+i); q[i]--; }

  ll ansA = 0, ansB = 1;

  for(int i=0 ;i<N; i++) {
    if (used[i]) continue;

    int t = i, start = i;
    vector<int> vec, to, idx;

    do{
      to.push_back(t);
      used[t] = true;
      t = revp[q[p[t]]];
    }while(t != start);

    sort(to.begin(), to.end());

    idx = to;

    for(int i=0; i<to.size(); i++) {
      vec.push_back(p[to[i]]);
      to[i] = p[to[i]];
    }

    sort(to.begin(), to.end());

    // a mod b
    int a = -1, b;

    b = vec.size();

    for(int i=0; i<vec.size(); i++) {
      if (vec == idx) { a = i; break; }

      for(int j=0; j<vec.size(); j++)
        vec[j] = q[vec[j]];
    }

    if (a == -1) {
      ansB = -1;
    } else {
      auto res = CRT(a, b, ansA, ansB);
      //auto res = CRT(ansA, ansB, a, b);
      ansA = res.first;
      ansB = res.second;
    }

    if (ansB == -1) {
      puts("-1");
      return 0;
    }
  }

  cout << ansA << endl;

  return 0;
}