#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
#define bn(x) ((1<<x)-1)
#define newline puts("")
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,const vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 2005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;


vi ans;
vi x;

// HL-decomposition
struct hl {
  int n, m;
  vvi to, d;
  vi vd, vk, pv, dep, pa;
  int root;
  hl() {}
  hl(int mx):n(mx),to(mx),vd(mx),vk(mx),dep(mx),pa(mx,-1) {}
  void add(int a, int b) {
    to[a].pb(b);
    pa[b] = a;
    // to[b].pb(a);
  }
  int dfs(int v, int de=0, int p=-1) {
    dep[v] = de;
    vector<P> rs;
    rep(i,sz(to[v])) {
      int u = to[v][i];
      // if (u == p) continue;
      rs.pb(P(dfs(u,de+1,v),u));
    }
    if (sz(rs)) {
      sort(rng(rs));
      vd[v] = vd[rs[0].se]; pv[vd[v]] = p;
      d[vd[v]].pb(v); vk[v] = -sz(d[vd[v]]);
      return rs[0].fi - (sz(rs) != 1 && rs[0].fi == rs[1].fi);
    } else {
      vd[v] = sz(d); vk[v] = -1; d.pb(vi(1,v)); pv.pb(p);
      return 1;
    }
  }
  void init(int v=0) {
    dfs(root = v);
    m = sz(d);
    rep(i,m) reverse(rng(d[i]));
    rep(i,n) vk[i] += sz(d[vd[i]]);
  }

  vi od;
  vvi oto;
  void ofs(int v) {
    for (int u : oto[v]) ofs(u);
    od.pb(v);
  }
  void initod() {
    oto = vvi(m);
    rep(i,m) {
      if (pv[i] == -1) continue;
      oto[vd[pv[i]]].pb(i);
    }
    ofs(vd[0]);
  }


  int efs(int v, int a=-1) {
    swap(x[v],a);
    if (!v) return a;
    return efs(pa[v],a);
  }
  void f(int v) {
    if (!v) return;
    ans.pb(v);
    x[v] = efs(pa[v],x[v]);
    // cerr<<"f: "<<v<<"; "<<x<<endl;
  }

  vi st, done;
  vi di;
  int stx(int a) { return st[vd[a]];}
  int stv(int v) { return stx(x[v]);}
  vi used;
  bool updst() {
    rep(i,m) if (st[i] == 1) st[i] = 2;
    used = vi(m);
    bool end = true;
    for (int i : od) {
      if (st[i] == 2) continue;
      if (!used[i]) {
        st[i] = 1;
        used[i] = 1;
        end = false;
      }
      if (pv[i] != -1) used[vd[pv[i]]] = 1;
    }
    return end;
  }

  void solve() {
    initod();
    di = vi(m); rep(i,m) di[i] = sz(d[i])-1;
    st = vi(m);
    done = vi(n);
    while (1) {
      if (updst()) break;
      // cerr<<"st: "<<st<<endl;
      while (!done[0]) {
        if (stv(0) == 0) {
          int v = -1;
          rep(i,n) {
            if (done[i] || stv(i) != 1) continue;
            if (v == -1) v = i;
            else if (dep[v] < dep[i]) v = i;
          }
          // cerr<<"v: "<<v<<endl;
          if (v == -1) break;
          f(v);
        } else {
          int i = vd[x[0]];
          int ni = di[i];
          for (int j = di[i]+1; j < sz(d[i]); ++j) {
            if (vk[x[d[i][j]]] < vk[x[0]]) ni = j;
            else break;
          }
          // cerr<<x[0]<<" "<<i<<" "<<ni<<endl;
          f(d[i][ni]);
          done[d[i][di[i]]] = 1;
          --di[i];
        }
      }
    }
  }
} g;
//

int main() {
  int n;
  scanf("%d",&n);
  g = hl(n);
  rrep(i,n-1) {
    int a;
    scanf("%d",&a);
    g.add(a,i);
  }
  g.init();
  vi a(n);
  cin>>a;
  x = vi(n);
  // rep(i,n) x[a[i]] = i;
  x = a;
  // cerr<<x<<endl;
  g.solve();
  // reverse(rng(ans));

  rep(i,n) assert(x[i] == i);

  cout<<sz(ans)<<endl; for (int v : ans) printf("%d\n",v);
  // cout<<"a"<<endl;
  // cerr<<sz(ans)<<endl;

  return 0;
}





















### Prompt

Please create a solution in Cpp to the following problem:

You are given a rooted tree with N vertices. The vertices are numbered 0, 1, ..., N-1. The root is Vertex 0, and the parent of Vertex i (i = 1, 2, ..., N-1) is Vertex p_i.

Initially, an integer a_i is written in Vertex i. Here, (a_0, a_1, ..., a_{N-1}) is a permutation of (0, 1, ..., N-1).

You can execute the following operation at most 25 000 times. Do it so that the value written in Vertex i becomes i.

* Choose a vertex and call it v. Consider the path connecting Vertex 0 and v.
* Rotate the values written on the path. That is, For each edge (i, p_i) along the path, replace the value written in Vertex p_i with the value written in Vertex i (just before this operation), and replace the value of v with the value written in Vertex 0 (just before this operation).
* You may choose Vertex 0, in which case the operation does nothing.

Constraints

* 2 \leq N \leq 2000
* 0 \leq p_i \leq i-1
* (a_0, a_1, ..., a_{N-1}) is a permutation of (0, 1, ..., N-1).

Input

Input is given from Standard Input in the following format:


N
p_1 p_2 ... p_{N-1}
a_0 a_1 ... a_{N-1}


Output

In the first line, print the number of operations, Q. In the second through (Q+1)-th lines, print the chosen vertices in order.

Examples

Input

5
0 1 2 3
2 4 0 1 3


Output

2
3
4


Input

5
0 1 2 2
4 3 1 2 0


Output

3
4
3
1

### Response

```cpp
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
#define bn(x) ((1<<x)-1)
#define newline puts("")
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,const vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 2005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;


vi ans;
vi x;

// HL-decomposition
struct hl {
  int n, m;
  vvi to, d;
  vi vd, vk, pv, dep, pa;
  int root;
  hl() {}
  hl(int mx):n(mx),to(mx),vd(mx),vk(mx),dep(mx),pa(mx,-1) {}
  void add(int a, int b) {
    to[a].pb(b);
    pa[b] = a;
    // to[b].pb(a);
  }
  int dfs(int v, int de=0, int p=-1) {
    dep[v] = de;
    vector<P> rs;
    rep(i,sz(to[v])) {
      int u = to[v][i];
      // if (u == p) continue;
      rs.pb(P(dfs(u,de+1,v),u));
    }
    if (sz(rs)) {
      sort(rng(rs));
      vd[v] = vd[rs[0].se]; pv[vd[v]] = p;
      d[vd[v]].pb(v); vk[v] = -sz(d[vd[v]]);
      return rs[0].fi - (sz(rs) != 1 && rs[0].fi == rs[1].fi);
    } else {
      vd[v] = sz(d); vk[v] = -1; d.pb(vi(1,v)); pv.pb(p);
      return 1;
    }
  }
  void init(int v=0) {
    dfs(root = v);
    m = sz(d);
    rep(i,m) reverse(rng(d[i]));
    rep(i,n) vk[i] += sz(d[vd[i]]);
  }

  vi od;
  vvi oto;
  void ofs(int v) {
    for (int u : oto[v]) ofs(u);
    od.pb(v);
  }
  void initod() {
    oto = vvi(m);
    rep(i,m) {
      if (pv[i] == -1) continue;
      oto[vd[pv[i]]].pb(i);
    }
    ofs(vd[0]);
  }


  int efs(int v, int a=-1) {
    swap(x[v],a);
    if (!v) return a;
    return efs(pa[v],a);
  }
  void f(int v) {
    if (!v) return;
    ans.pb(v);
    x[v] = efs(pa[v],x[v]);
    // cerr<<"f: "<<v<<"; "<<x<<endl;
  }

  vi st, done;
  vi di;
  int stx(int a) { return st[vd[a]];}
  int stv(int v) { return stx(x[v]);}
  vi used;
  bool updst() {
    rep(i,m) if (st[i] == 1) st[i] = 2;
    used = vi(m);
    bool end = true;
    for (int i : od) {
      if (st[i] == 2) continue;
      if (!used[i]) {
        st[i] = 1;
        used[i] = 1;
        end = false;
      }
      if (pv[i] != -1) used[vd[pv[i]]] = 1;
    }
    return end;
  }

  void solve() {
    initod();
    di = vi(m); rep(i,m) di[i] = sz(d[i])-1;
    st = vi(m);
    done = vi(n);
    while (1) {
      if (updst()) break;
      // cerr<<"st: "<<st<<endl;
      while (!done[0]) {
        if (stv(0) == 0) {
          int v = -1;
          rep(i,n) {
            if (done[i] || stv(i) != 1) continue;
            if (v == -1) v = i;
            else if (dep[v] < dep[i]) v = i;
          }
          // cerr<<"v: "<<v<<endl;
          if (v == -1) break;
          f(v);
        } else {
          int i = vd[x[0]];
          int ni = di[i];
          for (int j = di[i]+1; j < sz(d[i]); ++j) {
            if (vk[x[d[i][j]]] < vk[x[0]]) ni = j;
            else break;
          }
          // cerr<<x[0]<<" "<<i<<" "<<ni<<endl;
          f(d[i][ni]);
          done[d[i][di[i]]] = 1;
          --di[i];
        }
      }
    }
  }
} g;
//

int main() {
  int n;
  scanf("%d",&n);
  g = hl(n);
  rrep(i,n-1) {
    int a;
    scanf("%d",&a);
    g.add(a,i);
  }
  g.init();
  vi a(n);
  cin>>a;
  x = vi(n);
  // rep(i,n) x[a[i]] = i;
  x = a;
  // cerr<<x<<endl;
  g.solve();
  // reverse(rng(ans));

  rep(i,n) assert(x[i] == i);

  cout<<sz(ans)<<endl; for (int v : ans) printf("%d\n",v);
  // cout<<"a"<<endl;
  // cerr<<sz(ans)<<endl;

  return 0;
}





















```