#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long lint;

struct solver_t {
  int n;
  vector<vector<int>> children;
  vector<int> parent, depth, subtree_size;
  vector<int> values, positions;
  vector<int> operations;
  struct pending_match_t {
    int trigger_pos, trigger_value;
    vector<int> nodes;
  };
  queue<pending_match_t> pendings;
  vector<int> tree_walk;
  int total_pendings_weight;
  solver_t(const vector<int> &perm)
    : n(perm.size()), children(n), parent(n, -1), depth(n), subtree_size(n)
    , values(perm), positions(n), total_pendings_weight(0) {
    for (int i = 0; i < n; ++i)
      positions[values[i]] = i;
  }
  void precalc(int v, int depth_v) {
    depth[v] = depth_v;
    subtree_size[v] = 1;
    for (int u : children[v]) {
      precalc(u, depth[v] + 1);
      subtree_size[v] += subtree_size[u];
    }
  }
  int get_heaviest_child(int v) {
    assert(!children[v].empty());
    return *max_element(children[v].begin(), children[v].end(),
                        [&](const int &a, const int &b) {
                          return subtree_size[a] < subtree_size[b];
                        });
  }
  void biased_post_walk(int v, vector<int> *walk) {
    if (!children[v].empty()) {
      int heaviest_child = get_heaviest_child(v);
      biased_post_walk(heaviest_child, walk);
      for (int u : children[v])
        if (u != heaviest_child)
          biased_post_walk(u, walk);
    }
    walk->push_back(v);
  }
  void swap_nodes(int a, int b) {
    swap(values[a], values[b]);
    swap(positions[values[a]], positions[values[b]]);
  }
  void push_to_root(int v) {
    operations.push_back(v);
    while (v != 0) {
      swap_nodes(v, parent[v]);
      v = parent[v];
    }
  }
  void perform_first_pending() {
    const pending_match_t &pending = pendings.front();
    for (int v : pending.nodes)
      while (values[v] != v)
        push_to_root(v);
    total_pendings_weight -= pending.nodes.size();
    pendings.pop();
  }
  void flush_pendings() {
    while (!pendings.empty())
      perform_first_pending();
  }
  void solve_small_subtree(int root) {
    const int buffer = parent[root];
    if (subtree_size[root] + total_pendings_weight >= depth[buffer] + 1)
      flush_pendings();
    vector<int> subtree_walk;
    biased_post_walk(root, &subtree_walk);
    for (int v : subtree_walk) {
      while (!pendings.empty() &&
             values[pendings.front().trigger_pos] ==
                 pendings.front().trigger_value) {
        perform_first_pending();
      }
      push_to_root(positions[v]);
    }

    // Coallesce.
    for (int i = 0; i + 1 < (int)subtree_walk.size(); ++i) {
      int v = subtree_walk[i], u = subtree_walk[i + 1];
      assert(depth[positions[v]] > depth[positions[u]]);
      int nrep = depth[positions[v]] - depth[positions[u]] - 1;
      for (int rep = 0; rep < nrep; ++rep)
        push_to_root(parent[positions[v]]);
    }

    int trigger_value = subtree_walk.front();
    total_pendings_weight += subtree_walk.size();
    pendings.emplace(
        (pending_match_t){buffer, trigger_value, move(subtree_walk)});
  }
  void solve_big_subtree(int root) {
    flush_pendings();
    const int buffer = parent[root];
    vector<int> subtree_walk;
    biased_post_walk(root, &subtree_walk);
    static vector<bool> being_solved, being_fetched;
    if (being_solved.empty()) being_solved.resize(n, false);
    if (being_fetched.empty()) being_fetched.resize(n, false);
    for (int v : subtree_walk) being_solved[v] = true;

    // 1: Kick everyone out.
    auto target = tree_walk.begin();
    auto dispose = [&]() {
      while (being_solved[values[*target]]) {
        ++target;
        assert(target != tree_walk.end());
      }
      push_to_root(*target);
    };
    for (int i = subtree_walk.size() - 1; i >= 0; --i) {
      int v = subtree_walk[i];
      if (being_solved[values[v]]) {
        while (being_solved[values[buffer]]) dispose();
        push_to_root(v);
      }
    }

    // 2: Fetch them back.
    target = subtree_walk.begin();
    auto pull = [&]() {
      while (values[*target] == *target) {
        ++target;
        assert(target != subtree_walk.end());
      }
      push_to_root(*target);
    };
    for (int v : subtree_walk) {
      while (being_fetched[values[buffer]]) {
        pull();
      }
      push_to_root(positions[v]);
      being_fetched[v] = true;
    }
    while (values[subtree_walk.back()] != subtree_walk.back())
      pull();

    for (int v : subtree_walk) being_solved[v] = being_fetched[v] = false;
  }
  void solve_subtree(int v) {
    int buffer = parent[v];
    if (subtree_size[v] < depth[buffer] + 1) {
      solve_small_subtree(v);
    } else {
      solve_big_subtree(v);
    }
  }
  void solve(int v) {
    if (children[v].empty()) {
      flush_pendings();
    } else {
      int heaviest_child = get_heaviest_child(v);
      for (int u : children[v])
        if (u != heaviest_child)
          solve_subtree(u);
      solve(heaviest_child);
    }
    push_to_root(positions[v]);
  }
  void solve() {
    precalc(0, 0);
    biased_post_walk(0, &tree_walk);
    solve(0);
  }
};

int main() {
  int n;
  scanf("%d", &n);
  vector<int> parents(n, -1);
  for (int i = 1; i < n; ++i)
    scanf("%d", &parents[i]);
  vector<int> values(n);
  for (int i = 0; i < n; ++i)
    scanf("%d", &values[i]);
  vector<int> inv_values(n);
  for (int i = 0; i < n; ++i)
    inv_values[values[i]] = i;
  solver_t solver(inv_values);
  for (int i = 1; i < n; ++i) {
    solver.parent[i] = parents[i];
    solver.children[parents[i]].push_back(i);
  }
  solver.solve();
  vector<int> result = solver.operations;
  reverse(result.begin(), result.end());
  printf("%d\n", (int)result.size());
  for (int v : result)
    printf("%d\n", v);
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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 <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long lint;

struct solver_t {
  int n;
  vector<vector<int>> children;
  vector<int> parent, depth, subtree_size;
  vector<int> values, positions;
  vector<int> operations;
  struct pending_match_t {
    int trigger_pos, trigger_value;
    vector<int> nodes;
  };
  queue<pending_match_t> pendings;
  vector<int> tree_walk;
  int total_pendings_weight;
  solver_t(const vector<int> &perm)
    : n(perm.size()), children(n), parent(n, -1), depth(n), subtree_size(n)
    , values(perm), positions(n), total_pendings_weight(0) {
    for (int i = 0; i < n; ++i)
      positions[values[i]] = i;
  }
  void precalc(int v, int depth_v) {
    depth[v] = depth_v;
    subtree_size[v] = 1;
    for (int u : children[v]) {
      precalc(u, depth[v] + 1);
      subtree_size[v] += subtree_size[u];
    }
  }
  int get_heaviest_child(int v) {
    assert(!children[v].empty());
    return *max_element(children[v].begin(), children[v].end(),
                        [&](const int &a, const int &b) {
                          return subtree_size[a] < subtree_size[b];
                        });
  }
  void biased_post_walk(int v, vector<int> *walk) {
    if (!children[v].empty()) {
      int heaviest_child = get_heaviest_child(v);
      biased_post_walk(heaviest_child, walk);
      for (int u : children[v])
        if (u != heaviest_child)
          biased_post_walk(u, walk);
    }
    walk->push_back(v);
  }
  void swap_nodes(int a, int b) {
    swap(values[a], values[b]);
    swap(positions[values[a]], positions[values[b]]);
  }
  void push_to_root(int v) {
    operations.push_back(v);
    while (v != 0) {
      swap_nodes(v, parent[v]);
      v = parent[v];
    }
  }
  void perform_first_pending() {
    const pending_match_t &pending = pendings.front();
    for (int v : pending.nodes)
      while (values[v] != v)
        push_to_root(v);
    total_pendings_weight -= pending.nodes.size();
    pendings.pop();
  }
  void flush_pendings() {
    while (!pendings.empty())
      perform_first_pending();
  }
  void solve_small_subtree(int root) {
    const int buffer = parent[root];
    if (subtree_size[root] + total_pendings_weight >= depth[buffer] + 1)
      flush_pendings();
    vector<int> subtree_walk;
    biased_post_walk(root, &subtree_walk);
    for (int v : subtree_walk) {
      while (!pendings.empty() &&
             values[pendings.front().trigger_pos] ==
                 pendings.front().trigger_value) {
        perform_first_pending();
      }
      push_to_root(positions[v]);
    }

    // Coallesce.
    for (int i = 0; i + 1 < (int)subtree_walk.size(); ++i) {
      int v = subtree_walk[i], u = subtree_walk[i + 1];
      assert(depth[positions[v]] > depth[positions[u]]);
      int nrep = depth[positions[v]] - depth[positions[u]] - 1;
      for (int rep = 0; rep < nrep; ++rep)
        push_to_root(parent[positions[v]]);
    }

    int trigger_value = subtree_walk.front();
    total_pendings_weight += subtree_walk.size();
    pendings.emplace(
        (pending_match_t){buffer, trigger_value, move(subtree_walk)});
  }
  void solve_big_subtree(int root) {
    flush_pendings();
    const int buffer = parent[root];
    vector<int> subtree_walk;
    biased_post_walk(root, &subtree_walk);
    static vector<bool> being_solved, being_fetched;
    if (being_solved.empty()) being_solved.resize(n, false);
    if (being_fetched.empty()) being_fetched.resize(n, false);
    for (int v : subtree_walk) being_solved[v] = true;

    // 1: Kick everyone out.
    auto target = tree_walk.begin();
    auto dispose = [&]() {
      while (being_solved[values[*target]]) {
        ++target;
        assert(target != tree_walk.end());
      }
      push_to_root(*target);
    };
    for (int i = subtree_walk.size() - 1; i >= 0; --i) {
      int v = subtree_walk[i];
      if (being_solved[values[v]]) {
        while (being_solved[values[buffer]]) dispose();
        push_to_root(v);
      }
    }

    // 2: Fetch them back.
    target = subtree_walk.begin();
    auto pull = [&]() {
      while (values[*target] == *target) {
        ++target;
        assert(target != subtree_walk.end());
      }
      push_to_root(*target);
    };
    for (int v : subtree_walk) {
      while (being_fetched[values[buffer]]) {
        pull();
      }
      push_to_root(positions[v]);
      being_fetched[v] = true;
    }
    while (values[subtree_walk.back()] != subtree_walk.back())
      pull();

    for (int v : subtree_walk) being_solved[v] = being_fetched[v] = false;
  }
  void solve_subtree(int v) {
    int buffer = parent[v];
    if (subtree_size[v] < depth[buffer] + 1) {
      solve_small_subtree(v);
    } else {
      solve_big_subtree(v);
    }
  }
  void solve(int v) {
    if (children[v].empty()) {
      flush_pendings();
    } else {
      int heaviest_child = get_heaviest_child(v);
      for (int u : children[v])
        if (u != heaviest_child)
          solve_subtree(u);
      solve(heaviest_child);
    }
    push_to_root(positions[v]);
  }
  void solve() {
    precalc(0, 0);
    biased_post_walk(0, &tree_walk);
    solve(0);
  }
};

int main() {
  int n;
  scanf("%d", &n);
  vector<int> parents(n, -1);
  for (int i = 1; i < n; ++i)
    scanf("%d", &parents[i]);
  vector<int> values(n);
  for (int i = 0; i < n; ++i)
    scanf("%d", &values[i]);
  vector<int> inv_values(n);
  for (int i = 0; i < n; ++i)
    inv_values[values[i]] = i;
  solver_t solver(inv_values);
  for (int i = 1; i < n; ++i) {
    solver.parent[i] = parents[i];
    solver.children[parents[i]].push_back(i);
  }
  solver.solve();
  vector<int> result = solver.operations;
  reverse(result.begin(), result.end());
  printf("%d\n", (int)result.size());
  for (int v : result)
    printf("%d\n", v);
  return 0;
}

```