#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
int MOD = 10000000;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

vector <int> son[2050];
int par[2050];
int val[2050];
bool isdec[2050][2050];
int deccnt[2050];
int cnt[2050];
bool chk[2050];

vector <int> Vd[2050];
vector <int> Vrd[2050];
void DFS(int n, int on) {
	Vd[on].push_back(n);
	Vrd[n].push_back(on);
	isdec[on][n] = true;
	deccnt[on]++;
	for (auto it : son[n]) DFS(it, on);
}

vector <int> Vl;
int findpos(int n, int t) {
	if (son[n].empty()) return n;
	int mn = son[n][0];
	for (auto it : son[n]) if (val[mn] > val[it]) mn = it;
	if (val[mn] > t) return n;
	return findpos(mn, t);
}

vector <int> Va;
vector <int> Vur;
void myrotate(int x) {
	Va.push_back(x);
	
	Vur.clear();
	Vur.push_back(x);
	while (Vur.back() != 0) Vur.push_back(par[Vur.back()]);

	int v = val[0];
	for (int i = (int)Vur.size() - 2; i >= 0; i--) val[Vur[i + 1]] = val[Vur[i]];
	val[Vur[0]] = v;
}

int DEBUG = 0;
int main() {
	int N, i, j;

	if(!DEBUG) scanf("%d", &N);
	else {
		int seed;
		scanf("%d %d", &N, &seed);
		srand(seed);
	}
	for (i = 1; i < N; i++) {
		if(!DEBUG) scanf("%d", &par[i]);
		else par[i] = i - 1;
		son[par[i]].push_back(i);
	}

	if(!DEBUG) for (i = 0; i < N; i++) scanf("%d", &val[i]);
	else {
		for (i = 0; i < N; i++) val[i] = N - 1 - i;
		random_shuffle(val, val + N);
	}
	for (i = 0; i < N; i++) DFS(i, i);
	while (!chk[0]) {
		int t = val[0];
		Vl.clear();
		for (i = 0; i < N; i++) if (isdec[t][i] && cnt[i] == deccnt[i] - 1) Vl.push_back(i);

		bool cu = false;
		if (Vl.empty()) {
			cu = true;
			Vl.push_back(t);
		}

		random_shuffle(all(Vl));
		int x = Vl[0];

		if (cnt[x] == deccnt[x] - 1) {
			chk[x] = true;
			for (i = 0; i < N; i++) if (isdec[i][x]) cnt[i]++;
		}
		x = findpos(x, t);
		myrotate(x);
		if (cu) {
			while (chk[x]) {
				if (!isdec[val[x]][x]) {
					for (auto it : Vrd[x]) {
						if (!chk[it]) continue;
						chk[it] = false;
						for (auto it2 : Vrd[it]) cnt[it2]--;
					}
					//printf("Broke at %d\n", x);
					break;
					
				}
				if (x == 0) break;
				x = par[x];
			}
		}

		if (DEBUG && chk[0]) {
			printf("val: ");
			for (i = 0; i < N; i++) printf("%d ", val[i]);
			printf("\n");
			printf("chk: ");
			for (i = 0; i < N; i++) printf("%d ", (int)chk[i]);
			printf("\n");
			printf("-------------");
			printf("\n");

			for (i = 0; i < N; i++) if (val[i] != i) break;
			if (i < N) printf("ERROR OCCURED!! at %d\n", i);
		}
	}
	printf("%d\n", (int)Va.size());
	if(!DEBUG) for (auto it : Va) printf("%d\n", it);
	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
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
int MOD = 10000000;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

vector <int> son[2050];
int par[2050];
int val[2050];
bool isdec[2050][2050];
int deccnt[2050];
int cnt[2050];
bool chk[2050];

vector <int> Vd[2050];
vector <int> Vrd[2050];
void DFS(int n, int on) {
	Vd[on].push_back(n);
	Vrd[n].push_back(on);
	isdec[on][n] = true;
	deccnt[on]++;
	for (auto it : son[n]) DFS(it, on);
}

vector <int> Vl;
int findpos(int n, int t) {
	if (son[n].empty()) return n;
	int mn = son[n][0];
	for (auto it : son[n]) if (val[mn] > val[it]) mn = it;
	if (val[mn] > t) return n;
	return findpos(mn, t);
}

vector <int> Va;
vector <int> Vur;
void myrotate(int x) {
	Va.push_back(x);
	
	Vur.clear();
	Vur.push_back(x);
	while (Vur.back() != 0) Vur.push_back(par[Vur.back()]);

	int v = val[0];
	for (int i = (int)Vur.size() - 2; i >= 0; i--) val[Vur[i + 1]] = val[Vur[i]];
	val[Vur[0]] = v;
}

int DEBUG = 0;
int main() {
	int N, i, j;

	if(!DEBUG) scanf("%d", &N);
	else {
		int seed;
		scanf("%d %d", &N, &seed);
		srand(seed);
	}
	for (i = 1; i < N; i++) {
		if(!DEBUG) scanf("%d", &par[i]);
		else par[i] = i - 1;
		son[par[i]].push_back(i);
	}

	if(!DEBUG) for (i = 0; i < N; i++) scanf("%d", &val[i]);
	else {
		for (i = 0; i < N; i++) val[i] = N - 1 - i;
		random_shuffle(val, val + N);
	}
	for (i = 0; i < N; i++) DFS(i, i);
	while (!chk[0]) {
		int t = val[0];
		Vl.clear();
		for (i = 0; i < N; i++) if (isdec[t][i] && cnt[i] == deccnt[i] - 1) Vl.push_back(i);

		bool cu = false;
		if (Vl.empty()) {
			cu = true;
			Vl.push_back(t);
		}

		random_shuffle(all(Vl));
		int x = Vl[0];

		if (cnt[x] == deccnt[x] - 1) {
			chk[x] = true;
			for (i = 0; i < N; i++) if (isdec[i][x]) cnt[i]++;
		}
		x = findpos(x, t);
		myrotate(x);
		if (cu) {
			while (chk[x]) {
				if (!isdec[val[x]][x]) {
					for (auto it : Vrd[x]) {
						if (!chk[it]) continue;
						chk[it] = false;
						for (auto it2 : Vrd[it]) cnt[it2]--;
					}
					//printf("Broke at %d\n", x);
					break;
					
				}
				if (x == 0) break;
				x = par[x];
			}
		}

		if (DEBUG && chk[0]) {
			printf("val: ");
			for (i = 0; i < N; i++) printf("%d ", val[i]);
			printf("\n");
			printf("chk: ");
			for (i = 0; i < N; i++) printf("%d ", (int)chk[i]);
			printf("\n");
			printf("-------------");
			printf("\n");

			for (i = 0; i < N; i++) if (val[i] != i) break;
			if (i < N) printf("ERROR OCCURED!! at %d\n", i);
		}
	}
	printf("%d\n", (int)Va.size());
	if(!DEBUG) for (auto it : Va) printf("%d\n", it);
	return 0;
}
//*/
```