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

typedef pair<int, int> pii;
typedef long long ll;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cerr << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

const int maxn = 2010;

V<int> g[maxn];
bool one[maxn];
int a[maxn], dep[maxn];

int dfs(int v, int d) {
	int num = 0;
	dep[v] = d;
	for (int to : g[v]) {
		int res = dfs(to, d + 1);
		num += res; 
	}
	if (num == 0 && a[v] != v) ++num;
	if (num == 1) one[v] = 1;
	return num;
}

int main() {
	int N; cin >> N;
	V<int> p(N, -1);

	for (int i = 1; i < N; ++i) {
		cin >> p[i];
		g[p[i]].pb(i);
	}

	rep(i, N) cin >> a[i];

	V<int> ope;

	auto rot = [&](int v) {
		ope.pb(v);
		V<int> vec;
		while (v != -1) {
			vec.pb(v);
			v = p[v];
		}
		reverse(ALL(vec));
		int sz = vec.size();

		int x = a[0];
		rep(i, sz-1) {
			a[vec[i]] = a[vec[i+1]];
		}
		a[vec.back()] = x;

		reverse(ALL(vec));
		for (int v : vec) {
			bool t = (a[v] != v);
			for (auto to : g[v]) {
				if (one[to]) t = 1;
			}
			if (!t) {
				one[v] = 0;
			}
		}
	};

	while (true) {
		bool ok = 1;
		rep(i, N) if (i != a[i]) ok = 0;
		if (ok) {
			break;
		}

		memset(one, 0, sizeof(one));
		dfs(0, 0);

		V<int> cmp(N, -1);
		V<int> la(N, -1);
		{
			V<int> cand(N, 1);
			rep(i, N) cand[i] = one[i];
			rep(i, N) if (one[i] && p[i] != -1) cand[p[i]] = 0;
			int now = 0;
			rep(i, N) if (cand[i]) {
				int v = i;
				la[now] = v;
				while (v != -1 && one[v]) {
					cmp[v] = now;
					v = p[v];
				}
				now++;
			}
		}

		V<int> used(N, -1);
		rep(i, N) if (one[i]) used[a[i]] = 0;

		while (true) {
			{
				bool en = 1;
				rep(i, N) if (one[i]) {
					en = 0;
				}
				if (en) break;
			}
			int x = a[0];
			if (used[x] == 1) break;
			if (one[x]) {
				int v = la[cmp[x]];
				dump(v);
				while (v != -1) {
					int av = a[v];
					if (used[av] != 1 || (cmp[av] != cmp[x] || cmp[av] == cmp[x] && dep[av] < dep[x])) {
						used[x] = 1;
						rot(v);
						break;
					}
					v = p[v];
				}
			} else {
				int mdep = -1, cand = -1;
				rep(i, N) {
					int x = a[i];
					if (one[x] && used[x] != 1) {
						if (mdep < dep[i]) {
							mdep = dep[i];
							cand = i;
						}
					}
				}
				if (cand == -1) break;
				rot(cand);
			}
		}
 	}

 	cout << ope.size() << endl;
 	for (int x : ope) {
 		cout << x << endl;
 	}

	return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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;

typedef pair<int, int> pii;
typedef long long ll;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cerr << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

const int maxn = 2010;

V<int> g[maxn];
bool one[maxn];
int a[maxn], dep[maxn];

int dfs(int v, int d) {
	int num = 0;
	dep[v] = d;
	for (int to : g[v]) {
		int res = dfs(to, d + 1);
		num += res; 
	}
	if (num == 0 && a[v] != v) ++num;
	if (num == 1) one[v] = 1;
	return num;
}

int main() {
	int N; cin >> N;
	V<int> p(N, -1);

	for (int i = 1; i < N; ++i) {
		cin >> p[i];
		g[p[i]].pb(i);
	}

	rep(i, N) cin >> a[i];

	V<int> ope;

	auto rot = [&](int v) {
		ope.pb(v);
		V<int> vec;
		while (v != -1) {
			vec.pb(v);
			v = p[v];
		}
		reverse(ALL(vec));
		int sz = vec.size();

		int x = a[0];
		rep(i, sz-1) {
			a[vec[i]] = a[vec[i+1]];
		}
		a[vec.back()] = x;

		reverse(ALL(vec));
		for (int v : vec) {
			bool t = (a[v] != v);
			for (auto to : g[v]) {
				if (one[to]) t = 1;
			}
			if (!t) {
				one[v] = 0;
			}
		}
	};

	while (true) {
		bool ok = 1;
		rep(i, N) if (i != a[i]) ok = 0;
		if (ok) {
			break;
		}

		memset(one, 0, sizeof(one));
		dfs(0, 0);

		V<int> cmp(N, -1);
		V<int> la(N, -1);
		{
			V<int> cand(N, 1);
			rep(i, N) cand[i] = one[i];
			rep(i, N) if (one[i] && p[i] != -1) cand[p[i]] = 0;
			int now = 0;
			rep(i, N) if (cand[i]) {
				int v = i;
				la[now] = v;
				while (v != -1 && one[v]) {
					cmp[v] = now;
					v = p[v];
				}
				now++;
			}
		}

		V<int> used(N, -1);
		rep(i, N) if (one[i]) used[a[i]] = 0;

		while (true) {
			{
				bool en = 1;
				rep(i, N) if (one[i]) {
					en = 0;
				}
				if (en) break;
			}
			int x = a[0];
			if (used[x] == 1) break;
			if (one[x]) {
				int v = la[cmp[x]];
				dump(v);
				while (v != -1) {
					int av = a[v];
					if (used[av] != 1 || (cmp[av] != cmp[x] || cmp[av] == cmp[x] && dep[av] < dep[x])) {
						used[x] = 1;
						rot(v);
						break;
					}
					v = p[v];
				}
			} else {
				int mdep = -1, cand = -1;
				rep(i, N) {
					int x = a[i];
					if (one[x] && used[x] != 1) {
						if (mdep < dep[i]) {
							mdep = dep[i];
							cand = i;
						}
					}
				}
				if (cand == -1) break;
				rot(cand);
			}
		}
 	}

 	cout << ope.size() << endl;
 	for (int x : ope) {
 		cout << x << endl;
 	}

	return 0;
}
```