#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 2e3 + 5;

int par[MAXN], per[MAXN];
int used[MAXN];
int leaf[MAXN];

int ind_l[MAXN], ind_r[MAXN];
int good[MAXN];

vi ans;

int n;

void move(int pos) {
	if (pos <= 0) {
		return;
	}
	
	/*REP(i, 0, n) {
		printf("%d ", per[i]);
	}
	printf("\n%d\n", pos);*/
	
	ans.pb(pos);
	int tmp = per[0];
	for(int i = pos; i >= 0; i = par[i]) {
		int tmp2 = per[i];
		per[i] = tmp;
		tmp = tmp2;
	}
}

void solve(){
	scanf("%d", &n);
	par[0] = -1;
	REP(i, 1, n) {
		scanf("%d", &par[i]);
	}
	REP(i, 0, n) {
		scanf("%d", &per[i]);
	}
	while(1) {
		REP(i, 0, n) {
			leaf[i] = -1;
			good[i] = 0;
		}
		for(int i = n - 1; i >= 0; i--) {
			if (!used[i]) {
				if (leaf[i] == -1) {
					leaf[i] = i;
				}
				if (i > 0) {
					if (leaf[par[i]] == -1) {
						leaf[par[i]] = leaf[i];
					} else {
						leaf[par[i]] = -2;
					}
				}
			}
		}
		
		int cnt_good = 0, cnt_all = 0;
		REP(i, 0, n) {
			if (leaf[i] >= 0) {
				cnt_all++;
			}
		}
		for(int i = n - 1; i >= 0; i--) {
			if (leaf[i] == i) {
				int last = INF;
				ind_l[i] = INF;
				ind_r[i] = i;
				for(int j = i; j >= 0 && leaf[j] == i; j = par[j]) {
					int val = per[j];
					if (leaf[val] != i || val > last) {
						break;
					}
					cnt_good++;
					last = val;
					ind_l[i] = j;
					good[val] = 1;
				}
			}
		}
		
		int rr = n - 1;
		for(; cnt_good < cnt_all; ) {
			int val = per[0];
			/*if (good[val]) {
				if (val == 0) {
					break;
				}
				REP(i, 0, n) {
					printf("%d ", per[i]);
				}
				putchar('\n');
				exit(0);
			}*/
			if (leaf[val] >= 0) {
				int cur_leaf = leaf[val];
				int pos;
				for(pos = ind_r[cur_leaf]; pos >= ind_l[cur_leaf] && val < per[pos]; pos = par[pos]);
				//printf("%d\n", pos);
				move(pos);
				cnt_good++;
				good[val] = 1;
				if (ind_l[cur_leaf] > ind_r[cur_leaf]) {
					ind_l[cur_leaf] = ind_r[cur_leaf];
				} else {
					ind_l[cur_leaf] = par[ind_l[cur_leaf]];
				}
				continue;
			}
			for(; rr >= 0; rr--) {
				if (!good[per[rr]] && leaf[per[rr]] >= 0) {
					move(rr);
					break;
				}
			}
		}
		
		if (leaf[0] >= 0) {
			break;
		}
		REP(i, 0, n) {
			if (leaf[i] >= 0) {
				used[i] = 1;
			}
		}
	}
	
	assert(SZ(ans) <= 25000);
	
	printf("%d\n", SZ(ans));
	REP(i, 0, SZ(ans)) {
		printf("%d\n", ans[i]);
	}
	//putchar('\n');
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}

### Prompt

Your task is to create 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>
using namespace std;

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 2e3 + 5;

int par[MAXN], per[MAXN];
int used[MAXN];
int leaf[MAXN];

int ind_l[MAXN], ind_r[MAXN];
int good[MAXN];

vi ans;

int n;

void move(int pos) {
	if (pos <= 0) {
		return;
	}
	
	/*REP(i, 0, n) {
		printf("%d ", per[i]);
	}
	printf("\n%d\n", pos);*/
	
	ans.pb(pos);
	int tmp = per[0];
	for(int i = pos; i >= 0; i = par[i]) {
		int tmp2 = per[i];
		per[i] = tmp;
		tmp = tmp2;
	}
}

void solve(){
	scanf("%d", &n);
	par[0] = -1;
	REP(i, 1, n) {
		scanf("%d", &par[i]);
	}
	REP(i, 0, n) {
		scanf("%d", &per[i]);
	}
	while(1) {
		REP(i, 0, n) {
			leaf[i] = -1;
			good[i] = 0;
		}
		for(int i = n - 1; i >= 0; i--) {
			if (!used[i]) {
				if (leaf[i] == -1) {
					leaf[i] = i;
				}
				if (i > 0) {
					if (leaf[par[i]] == -1) {
						leaf[par[i]] = leaf[i];
					} else {
						leaf[par[i]] = -2;
					}
				}
			}
		}
		
		int cnt_good = 0, cnt_all = 0;
		REP(i, 0, n) {
			if (leaf[i] >= 0) {
				cnt_all++;
			}
		}
		for(int i = n - 1; i >= 0; i--) {
			if (leaf[i] == i) {
				int last = INF;
				ind_l[i] = INF;
				ind_r[i] = i;
				for(int j = i; j >= 0 && leaf[j] == i; j = par[j]) {
					int val = per[j];
					if (leaf[val] != i || val > last) {
						break;
					}
					cnt_good++;
					last = val;
					ind_l[i] = j;
					good[val] = 1;
				}
			}
		}
		
		int rr = n - 1;
		for(; cnt_good < cnt_all; ) {
			int val = per[0];
			/*if (good[val]) {
				if (val == 0) {
					break;
				}
				REP(i, 0, n) {
					printf("%d ", per[i]);
				}
				putchar('\n');
				exit(0);
			}*/
			if (leaf[val] >= 0) {
				int cur_leaf = leaf[val];
				int pos;
				for(pos = ind_r[cur_leaf]; pos >= ind_l[cur_leaf] && val < per[pos]; pos = par[pos]);
				//printf("%d\n", pos);
				move(pos);
				cnt_good++;
				good[val] = 1;
				if (ind_l[cur_leaf] > ind_r[cur_leaf]) {
					ind_l[cur_leaf] = ind_r[cur_leaf];
				} else {
					ind_l[cur_leaf] = par[ind_l[cur_leaf]];
				}
				continue;
			}
			for(; rr >= 0; rr--) {
				if (!good[per[rr]] && leaf[per[rr]] >= 0) {
					move(rr);
					break;
				}
			}
		}
		
		if (leaf[0] >= 0) {
			break;
		}
		REP(i, 0, n) {
			if (leaf[i] >= 0) {
				used[i] = 1;
			}
		}
	}
	
	assert(SZ(ans) <= 25000);
	
	printf("%d\n", SZ(ans));
	REP(i, 0, SZ(ans)) {
		printf("%d\n", ans[i]);
	}
	//putchar('\n');
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}

```