#ifdef DBG1
  #define LOCAL
#endif

#ifdef LOCAL
  #define _GLIBCXX_DEBUG
#endif

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#ifdef DBG1
    #define dbg(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dbg(...)
#endif

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;

const int MAX_OPERS = 25000;

bool isGood(const vector <int> & a) {
  for (int i = 0; i < int(a.size()); ++i) {
    if (i != a[i]) {
      return false;
    }
  }
  return true;
}

void rotateToRoot(int v, vector <int> & a, const vector <int> & par) {
  if (v == 0) { return; }
  rotateToRoot(par[v], a, par);
  a[par[v]] = a[v];
}

void makeMove(vector <int> & opers, vector <int> & a, const vector <int> & par, int num) {
  opers.push_back(num);
  int tmp = a[0];
  rotateToRoot(num, a, par);
  a[num] = tmp;
}

bool is_parent(int u, int v, const vector<int> & inT, const vector<int> & outT) {
  return inT[u] <= inT[v] && outT[v] <= outT[u];
}

struct Move {
  int depth, v;
  bool ok;

  bool operator < (const Move & o) const {
    if (depth != o.depth) {
      return depth < o.depth;
    }
    return v < o.v;
  }
};

Move dfs2(int s, int dep, const vector <int> & a, const vector <vector<int>> & child, const vector<int> & inT, const vector <int> & outT) {
  if (child[s].empty()) {
    bool ok = is_parent(a[s], s, inT, outT) && is_parent(a[0], a[s], inT, outT);
    Move res = Move({dep, s, ok});
    dbg("s %d returns %d %d %d\n", s, res.depth, res.v, res.ok ? 1 : 0);
    return res;
  }

  Move res({-1, -1, true});
  bool ok = 1;
  for (int v : child[s]) {
    Move cur = dfs2(v, dep + 1, a, child, inT, outT);
    if (!is_parent(a[0], a[v], inT, outT)) {
      res.ok = false;
      res = max(res, Move({dep, v, false}));
    }
    if (!is_parent(a[s], a[v], inT, outT) && res.ok) {
      res.ok = 0;
      res = max(res, Move({dep, s, false}));
    }
    if (!cur.ok) {
      res.ok = false;
      res = max(res, cur);
    }
  }
  if (res.ok) {
    res = Move({dep, s, true});
  }

  if (!is_parent(res.v, a[res.v], inT, outT) && !is_parent(a[res.v], res.v, inT, outT)) {
    res.depth += int(a.size());
  }
  dbg("s %d returns %d %d %d\n", s, res.depth, res.v, res.ok ? 1 : 0);
  return res;
}

Move findMove(const vector<int> & a, const vector <vector<int>> & child, const vector<int> & inT, const vector<int> & outT) {
  return dfs2(a[0], 0, a, child, inT, outT);
}

void dfs(int v, const vector <vector<int>> & child, vector<int> & inT, vector <int> & outT, int &timer) {
  inT[v] = ++timer;
  for (int u : child[v]) {
    dfs(u, child, inT, outT, timer);
  }
  outT[v] = ++timer;
}

bool solve() {
  int n;
  if (scanf("%d", &n) != 1) { return false; }
  vector <vector<int>> child(n);
  vector <int> par(n, -1);
  for (int i = 1; i < n; ++i) {
    scanf("%d", &par[i]);
    child[par[i]].push_back(i);
  }
  vector <int> a(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }

  vector <int> inT(n), outT(n);
  int timer = 0;
  dfs(0, child, inT, outT, timer);

  vector <int> opers;
  while (!isGood(a)) {
  #if 1
    if (n <= 30) {
      dbg("arr ");
      for (int x : a) {
        dbg("%d ", x);
      }
      dbg("\n");
    }
  #endif
    assert(int(opers.size()) < MAX_OPERS);
    Move move = findMove(a, child, inT, outT);
    dbg("move = %d %d %d\n", move.depth, move.v, move.ok ? 1 : 0);
    assert(move.v != 0);
    makeMove(opers, a, par, move.v);
  }
  printf("%d\n", int(opers.size()));
  for (int x : opers) {
    printf("%d\n", x);
  }
  return true;
}

int main() {
  while (solve());
  return 0;
}
### Prompt

Your challenge is to write a CPP solution 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
#ifdef DBG1
  #define LOCAL
#endif

#ifdef LOCAL
  #define _GLIBCXX_DEBUG
#endif

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#ifdef DBG1
    #define dbg(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dbg(...)
#endif

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;

const int MAX_OPERS = 25000;

bool isGood(const vector <int> & a) {
  for (int i = 0; i < int(a.size()); ++i) {
    if (i != a[i]) {
      return false;
    }
  }
  return true;
}

void rotateToRoot(int v, vector <int> & a, const vector <int> & par) {
  if (v == 0) { return; }
  rotateToRoot(par[v], a, par);
  a[par[v]] = a[v];
}

void makeMove(vector <int> & opers, vector <int> & a, const vector <int> & par, int num) {
  opers.push_back(num);
  int tmp = a[0];
  rotateToRoot(num, a, par);
  a[num] = tmp;
}

bool is_parent(int u, int v, const vector<int> & inT, const vector<int> & outT) {
  return inT[u] <= inT[v] && outT[v] <= outT[u];
}

struct Move {
  int depth, v;
  bool ok;

  bool operator < (const Move & o) const {
    if (depth != o.depth) {
      return depth < o.depth;
    }
    return v < o.v;
  }
};

Move dfs2(int s, int dep, const vector <int> & a, const vector <vector<int>> & child, const vector<int> & inT, const vector <int> & outT) {
  if (child[s].empty()) {
    bool ok = is_parent(a[s], s, inT, outT) && is_parent(a[0], a[s], inT, outT);
    Move res = Move({dep, s, ok});
    dbg("s %d returns %d %d %d\n", s, res.depth, res.v, res.ok ? 1 : 0);
    return res;
  }

  Move res({-1, -1, true});
  bool ok = 1;
  for (int v : child[s]) {
    Move cur = dfs2(v, dep + 1, a, child, inT, outT);
    if (!is_parent(a[0], a[v], inT, outT)) {
      res.ok = false;
      res = max(res, Move({dep, v, false}));
    }
    if (!is_parent(a[s], a[v], inT, outT) && res.ok) {
      res.ok = 0;
      res = max(res, Move({dep, s, false}));
    }
    if (!cur.ok) {
      res.ok = false;
      res = max(res, cur);
    }
  }
  if (res.ok) {
    res = Move({dep, s, true});
  }

  if (!is_parent(res.v, a[res.v], inT, outT) && !is_parent(a[res.v], res.v, inT, outT)) {
    res.depth += int(a.size());
  }
  dbg("s %d returns %d %d %d\n", s, res.depth, res.v, res.ok ? 1 : 0);
  return res;
}

Move findMove(const vector<int> & a, const vector <vector<int>> & child, const vector<int> & inT, const vector<int> & outT) {
  return dfs2(a[0], 0, a, child, inT, outT);
}

void dfs(int v, const vector <vector<int>> & child, vector<int> & inT, vector <int> & outT, int &timer) {
  inT[v] = ++timer;
  for (int u : child[v]) {
    dfs(u, child, inT, outT, timer);
  }
  outT[v] = ++timer;
}

bool solve() {
  int n;
  if (scanf("%d", &n) != 1) { return false; }
  vector <vector<int>> child(n);
  vector <int> par(n, -1);
  for (int i = 1; i < n; ++i) {
    scanf("%d", &par[i]);
    child[par[i]].push_back(i);
  }
  vector <int> a(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }

  vector <int> inT(n), outT(n);
  int timer = 0;
  dfs(0, child, inT, outT, timer);

  vector <int> opers;
  while (!isGood(a)) {
  #if 1
    if (n <= 30) {
      dbg("arr ");
      for (int x : a) {
        dbg("%d ", x);
      }
      dbg("\n");
    }
  #endif
    assert(int(opers.size()) < MAX_OPERS);
    Move move = findMove(a, child, inT, outT);
    dbg("move = %d %d %d\n", move.depth, move.v, move.ok ? 1 : 0);
    assert(move.v != 0);
    makeMove(opers, a, par, move.v);
  }
  printf("%d\n", int(opers.size()));
  for (int x : opers) {
    printf("%d\n", x);
  }
  return true;
}

int main() {
  while (solve());
  return 0;
}
```