#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define forn(i, a, n) for (int i = (int)(a); i < (int)(n); ++i)
#define ford(i, a, n) for (int i = (int)(n) - 1; i >= (int)(a); --i)
#define fore(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define fs first
#define sn second
#define trace(a)\
    for (auto i : a) cerr << i << ' ';\
    cerr << '\n'
#define eb emplace_back

#ifndef M_PI
const ld M_PI = acos(-1.0);
#endif

template<typename T>
inline void setmax(T& a, T b) {
    if (a < b) a = b;
}

template<typename T>
inline void setmin(T& a, T b) {
    if (a > b) a = b;
}

const ld eps = 1e-9;
const int INF = 2000000000;
const ll LINF = 1ll * INF * INF;
const ll MOD = 1000000007;

const int N = 2018;
int p[N], a[N], sz[N];
vector<int> ch[N];
int paths = -1;
int path[N], path_level[N], vertex_level[N];
int top[N], bot[N], heavy_son[N];

int dfs1(int u) {
    sz[u] = 1;
    for (int v : ch[u])
        sz[u] += dfs1(v);
    return sz[u];
}

void dfs2(int u) {
    int mx = -1, son = -1;
    for (int v : ch[u]) {
        dfs2(v);
        if (sz[v] > mx) {
            mx = sz[v];
            son = v;
        }
    }
    heavy_son[u] = son;
    if (son == -1) {
        path[u] = ++paths;
        bot[path[u]] = u;
    }
    else
        path[u] = path[son];
}

int dfs3(int u) {
    int mx = -1;
    for (int v : ch[u])
        setmax(mx, dfs3(v));
    if (u == 0 || path[u] != path[p[u]]) {
        top[path[u]] = u;
        ++mx;
        path_level[path[u]] = mx;
    }
    return mx;
}

int qs = 0;
vector<int> ans;
void push(int v) {
    if (v == 0) return;
    ++qs;
    ans.eb(v);
    int save = a[v];
    a[v] = a[0];
    v = p[v];
    while (v) {
        swap(a[v], save);
        v = p[v];
    }
    swap(save, a[v]);
}

int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0); 
    srand((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
    int n;
    cin >> n;
    //n = 2000;
    forn(i, 1, n) cin >> p[i];
    //forn(i, 1, n) p[i] = i - 1;
    //forn(i, 1, n) p[i] = rand() % i;
    //forn(i, 1, n) p[i] = i / 2;
    forn(i, 0, n) cin >> a[i];
    //iota(a, a + n, 0);
    //random_shuffle(a, a + n);
    forn(i, 1, n) ch[p[i]].eb(i);
    dfs1(0);
    dfs2(0);
    dfs3(0);
    forn(i, 0, n) vertex_level[i] = path_level[path[i]];
    //cerr << "here\n";
    //forn(i, 0, n) cout << path[i] << ' ' << vertex_level[i] << '\n';
    for (int L = 0; L <= vertex_level[0]; ++L) {
        vector<int> used(n);
        while (1) {
            if (used[0]) {
                forn(i, 0, n) assert(a[i] == i);
                assert(qs <= 25000);
                //cerr << "qs: " << qs << '\n';
                cout << ans.size() << '\n';
                for (int x : ans) cout << x << '\n';
                return 0;
            }
            if (vertex_level[a[0]] != L) {
                int found = -1;
                forn(i, 0, n)
                    if (vertex_level[a[i]] == L && !used[i])
                        found = i;
                if (found == -1) break;
                push(found);
            } else {
                int v = bot[path[a[0]]];
                while (v && used[v] && a[v] > a[0]) v = p[v];
                push(v);
                while (v && used[v]) v = p[v];
                used[v] = 1;
            }
        }
    }
    assert(false);
}

### Prompt

Generate 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
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define forn(i, a, n) for (int i = (int)(a); i < (int)(n); ++i)
#define ford(i, a, n) for (int i = (int)(n) - 1; i >= (int)(a); --i)
#define fore(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define fs first
#define sn second
#define trace(a)\
    for (auto i : a) cerr << i << ' ';\
    cerr << '\n'
#define eb emplace_back

#ifndef M_PI
const ld M_PI = acos(-1.0);
#endif

template<typename T>
inline void setmax(T& a, T b) {
    if (a < b) a = b;
}

template<typename T>
inline void setmin(T& a, T b) {
    if (a > b) a = b;
}

const ld eps = 1e-9;
const int INF = 2000000000;
const ll LINF = 1ll * INF * INF;
const ll MOD = 1000000007;

const int N = 2018;
int p[N], a[N], sz[N];
vector<int> ch[N];
int paths = -1;
int path[N], path_level[N], vertex_level[N];
int top[N], bot[N], heavy_son[N];

int dfs1(int u) {
    sz[u] = 1;
    for (int v : ch[u])
        sz[u] += dfs1(v);
    return sz[u];
}

void dfs2(int u) {
    int mx = -1, son = -1;
    for (int v : ch[u]) {
        dfs2(v);
        if (sz[v] > mx) {
            mx = sz[v];
            son = v;
        }
    }
    heavy_son[u] = son;
    if (son == -1) {
        path[u] = ++paths;
        bot[path[u]] = u;
    }
    else
        path[u] = path[son];
}

int dfs3(int u) {
    int mx = -1;
    for (int v : ch[u])
        setmax(mx, dfs3(v));
    if (u == 0 || path[u] != path[p[u]]) {
        top[path[u]] = u;
        ++mx;
        path_level[path[u]] = mx;
    }
    return mx;
}

int qs = 0;
vector<int> ans;
void push(int v) {
    if (v == 0) return;
    ++qs;
    ans.eb(v);
    int save = a[v];
    a[v] = a[0];
    v = p[v];
    while (v) {
        swap(a[v], save);
        v = p[v];
    }
    swap(save, a[v]);
}

int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0); 
    srand((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
    int n;
    cin >> n;
    //n = 2000;
    forn(i, 1, n) cin >> p[i];
    //forn(i, 1, n) p[i] = i - 1;
    //forn(i, 1, n) p[i] = rand() % i;
    //forn(i, 1, n) p[i] = i / 2;
    forn(i, 0, n) cin >> a[i];
    //iota(a, a + n, 0);
    //random_shuffle(a, a + n);
    forn(i, 1, n) ch[p[i]].eb(i);
    dfs1(0);
    dfs2(0);
    dfs3(0);
    forn(i, 0, n) vertex_level[i] = path_level[path[i]];
    //cerr << "here\n";
    //forn(i, 0, n) cout << path[i] << ' ' << vertex_level[i] << '\n';
    for (int L = 0; L <= vertex_level[0]; ++L) {
        vector<int> used(n);
        while (1) {
            if (used[0]) {
                forn(i, 0, n) assert(a[i] == i);
                assert(qs <= 25000);
                //cerr << "qs: " << qs << '\n';
                cout << ans.size() << '\n';
                for (int x : ans) cout << x << '\n';
                return 0;
            }
            if (vertex_level[a[0]] != L) {
                int found = -1;
                forn(i, 0, n)
                    if (vertex_level[a[i]] == L && !used[i])
                        found = i;
                if (found == -1) break;
                push(found);
            } else {
                int v = bot[path[a[0]]];
                while (v && used[v] && a[v] > a[0]) v = p[v];
                push(v);
                while (v && used[v]) v = p[v];
                used[v] = 1;
            }
        }
    }
    assert(false);
}

```