#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=2000;
const int MAXQ=25000;

typedef struct TNode* PTNode;
struct TNode {
	int prio,sz,val;
	PTNode l,r;
};

int tsz(PTNode x) { return x==NULL?0:x->sz; }
void updsz(PTNode x) { if(x!=NULL) x->sz=tsz(x->l)+1+tsz(x->r); }
void merge(PTNode &x,PTNode l,PTNode r) {
	//printf("merging trees of size %d and %d [%d,%d] [%d,%d]\n",tsz(l),tsz(r),l==NULL?-1:l->l==NULL?-2:tsz(l->l),l==NULL?-1:l->r==NULL?-2:tsz(l->r),r==NULL?-1:tsz(r->l),r==NULL?-1:tsz(r->r));
	if(l==NULL) x=r; else if(r==NULL) x=l; else { if(l->prio>r->prio) merge(l->r,l->r,r),x=l; else merge(r->l,l,r->l),x=r; }
	updsz(l);
	updsz(x);
}
void split(PTNode x,PTNode &l,PTNode &r,int cnt) {
	if(x==NULL) { l=r=NULL; return; }
	if(cnt<=tsz(x->l)) split(x->l,l,x->l,cnt),r=x; else split(x->r,x->r,r,cnt-1-tsz(x->l)),l=x;
	updsz(x);
}
void print(PTNode x,int d=0) { if(d>10) exit(0); if(x==NULL) return; print(x->l,d+1); printf(" %d",x->val); print(x->r,d+1); }


int n;
int par[MAXN];
int sval[MAXN];

vector<int> ch[MAXN];
int sz[MAXN],dep[MAXN],heavy[MAXN];

int hid[MAXN],hroot[MAXN],nh;
int hoff[MAXN+1],hsz[MAXN],hnode[MAXN];

TNode t[MAXN];
PTNode ht[MAXN];


void dfsinit(int at) {
	sz[at]=1; dep[at]=par[at]==-1?0:dep[par[at]]+1; heavy[at]=-1;
	REPSZ(i,ch[at]) {
		int to=ch[at][i];
		dfsinit(to);
		sz[at]+=sz[to];
		if(heavy[at]==-1||sz[to]>sz[heavy[at]]) heavy[at]=to;
	}
}

void dfsheavy(int at) {
	int h=nh++; ht[h]=NULL; hsz[h]=0;
	for(int x=at;x!=-1;x=heavy[x]) {
		hid[x]=h,hroot[x]=at,++hsz[h],hnode[hoff[h]+dep[x]-dep[hroot[x]]]=x;
		t[x].prio=rand(),t[x].sz=1,t[x].val=sval[x],t[x].l=t[x].r=NULL; PTNode tmp=ht[h]; merge(ht[h],tmp,&t[x]);
		//printf("added\n"); print(ht[h]); puts("");
	}
	hoff[nh]=hoff[h]+hsz[h];
	for(int x=at;x!=-1;x=heavy[x]) {
		REPSZ(i,ch[x]) {
			int to=ch[x][i]; if(to==heavy[x]) continue;
			dfsheavy(to);
		}
	}
}


int getval(int x) {
	//printf("getval(%d)\n",x);
	int h=hid[x],idx=dep[x]-dep[hroot[x]];
	PTNode l,m,r;
	split(ht[h],l,m,idx);
	split(m,m,r,1);
	int ret=m->val;
	merge(m,m,r);
	merge(ht[h],l,m);
	return ret;
}
void setval(int x,int v) {
	int h=hid[x],idx=dep[x]-dep[hroot[x]];
	PTNode l,m,r;
	split(ht[h],l,m,idx);
	split(m,m,r,1);
	m->val=v;
	merge(m,m,r);
	merge(ht[h],l,m);
}
void trotate(PTNode &x,int cnt) {
	PTNode l,m,r;
	split(x,l,r,cnt);
	split(l,l,m,1);
	merge(l,m,l);
	merge(x,l,r);
}

int ans[MAXQ],nans;
void rotate(int x) {
	assert(nans<MAXQ); ans[nans++]=x;
	int leafval=getval(0);
	while(x!=-1) {
		//printf("leafval=%d\n",leafval);
		int h=hid[x];
		int rootval=getval(hroot[x]);
		//printf("rootval=%d\n",rootval);
		trotate(ht[h],dep[x]-dep[hroot[x]]+1);
		setval(x,leafval);
		x=par[hroot[x]],leafval=rootval;
	}
}

int hcur[MAXN],hrem[MAXN],nhcur;
bool iscurnode[MAXN];
int curdeg[MAXN];
int q[MAXN],qhead,qtail;

int bit[MAXN+1];
void bmod(int idx,int by) { ++idx; while(idx<=n) { bit[idx]+=by; idx+=idx&-idx; } }
int bget(int idx) { ++idx; int ret=0; while(idx>0) { ret+=bit[idx]; idx-=idx&-idx; } return ret; }
int bgetrange(int lidx,int ridx) { return bget(ridx)-bget(lidx-1); }

void findcurrent(int at) {
	bool iscurrent=true;
	for(int x=at;x!=-1;x=heavy[x]) {
		REPSZ(i,ch[x]) {
			int to=ch[x][i]; if(to==heavy[x]) continue;
			if(hrem[hid[to]]!=0) iscurrent=false;
		}
	}
	if(iscurrent) {
		hcur[nhcur++]=hid[at];
		for(int x=at;x!=-1;x=heavy[x]) {
			if(heavy[x]!=-1) ++curdeg[x];
			if(curdeg[x]==0) q[qhead++]=x;
			iscurnode[x]=true;
		}
	} else {
		for(int x=at;x!=-1;x=heavy[x]) {
			if(heavy[x]!=-1) ++curdeg[x];
			REPSZ(i,ch[x]) {
				int to=ch[x][i]; if(to==heavy[x]||hrem[hid[to]]==0) continue;
				++curdeg[x];
				findcurrent(to);
			}
			if(curdeg[x]==0) q[qhead++]=x;
		}
	}
}

void process() {
	int tmpidx=0;
	//int rep=0;
	while(tmpidx<nhcur) {
		//if(++rep>20) exit(0);
		int val=getval(0);
		//printf("val=%d\n",val);
		if(iscurnode[val]) {
			int h=hid[val];
			int have=bgetrange(hoff[h]+dep[val]-dep[hroot[val]],hoff[h]+hsz[h]-1);
			int pos=hsz[h]-1-have;
			//printf("current rotate to %d (have=%d [%d..%d])\n",hnode[hoff[h]+pos],have,hoff[h]+dep[val]-dep[hroot[val]],hoff[h]+hsz[h]-1);
			rotate(hnode[hoff[h]+pos]);
			--hrem[h];
			bmod(hoff[h]+dep[val]-dep[hroot[val]],+1);
		} else {
			while(true) {
				assert(qtail<qhead);
				int at=q[qtail++];
				if(par[at]!=-1&&--curdeg[par[at]]==0) q[qhead++]=par[at];
				if(iscurnode[at]) {
					int h=hid[at];
					int have=hsz[h]-hrem[h];
					int pos=hsz[h]-have;
					//printf("!! at=%d have=%d pos=%d delta=%d\n",at,have,pos,dep[at]-dep[hroot[at]]);
					if(dep[at]-dep[hroot[at]]>=pos) continue;
				}
				//printf("rotate to %d\n",at);
				rotate(at);
				break;
			}
		}
		while(tmpidx<nhcur&&hrem[hcur[tmpidx]]==0) ++tmpidx;
	}
}

void solve() {
	REP(i,n) ch[i].clear(); REP(i,n) if(par[i]!=-1) ch[par[i]].PB(i);
	dfsinit(0);
	nh=0; hoff[0]=0; dfsheavy(0);

	//REP(i,n) printf("%d: sz=%d dep=%d heavy=%d hid=%d hroot=%d\n",i,sz[i],dep[i],heavy[i],hid[i],hroot[i]);
	//REP(i,nh) { printf("h%d:",i); print(ht[i]); puts(""); }

	//printf("val:"); REP(i,n) printf(" %d",getval(i)); puts("");

	REP(i,nh) hrem[i]=hsz[i]; nans=0; REPE(i,n) bit[i]=0;
	while(hrem[hid[0]]>0) {
		nhcur=0; REP(i,n) iscurnode[i]=false,curdeg[i]=0; qhead=qtail=0; findcurrent(0); if(nhcur==0) break;
		//printf("hcur:"); REP(i,nhcur) { int h=hcur[i]; REP(j,hsz[h]) printf("%c%d",j==0?' ':',',hnode[hoff[h]+j]); } puts("");
		//printf("deg:"); REP(i,n) printf(" %d",curdeg[i]); puts("");
		process();
	}
}

void run() {
	scanf("%d",&n); par[0]=-1; FOR(i,1,n) scanf("%d",&par[i]); REP(i,n) scanf("%d",&sval[i]);
	solve();
	printf("%d\n",nans); REP(i,nans) printf("%d\n",ans[i]);
}

void stress() {
	REP(rep,100) {
		n=MAXN; par[0]=-1; FOR(i,1,n) par[i]=rand()%i; REP(i,n) sval[i]=i; REP(i,n) { int idx=i+rand()%(n-i); swap(sval[i],sval[idx]); }
		//printf("%d\n",n); FOR(i,1,n) { if(i!=1) printf(" "); printf("%d",par[i]); } puts(""); REP(i,n) { if(i!=0) printf(" "); printf("%d",sval[i]); } puts("");
		solve();
		printf("nq=%d\n",nans);
	}
}

int main() {
	run();
	//stress();
	return 0;
}

### Prompt

Please provide a Cpp coded solution 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 <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=2000;
const int MAXQ=25000;

typedef struct TNode* PTNode;
struct TNode {
	int prio,sz,val;
	PTNode l,r;
};

int tsz(PTNode x) { return x==NULL?0:x->sz; }
void updsz(PTNode x) { if(x!=NULL) x->sz=tsz(x->l)+1+tsz(x->r); }
void merge(PTNode &x,PTNode l,PTNode r) {
	//printf("merging trees of size %d and %d [%d,%d] [%d,%d]\n",tsz(l),tsz(r),l==NULL?-1:l->l==NULL?-2:tsz(l->l),l==NULL?-1:l->r==NULL?-2:tsz(l->r),r==NULL?-1:tsz(r->l),r==NULL?-1:tsz(r->r));
	if(l==NULL) x=r; else if(r==NULL) x=l; else { if(l->prio>r->prio) merge(l->r,l->r,r),x=l; else merge(r->l,l,r->l),x=r; }
	updsz(l);
	updsz(x);
}
void split(PTNode x,PTNode &l,PTNode &r,int cnt) {
	if(x==NULL) { l=r=NULL; return; }
	if(cnt<=tsz(x->l)) split(x->l,l,x->l,cnt),r=x; else split(x->r,x->r,r,cnt-1-tsz(x->l)),l=x;
	updsz(x);
}
void print(PTNode x,int d=0) { if(d>10) exit(0); if(x==NULL) return; print(x->l,d+1); printf(" %d",x->val); print(x->r,d+1); }


int n;
int par[MAXN];
int sval[MAXN];

vector<int> ch[MAXN];
int sz[MAXN],dep[MAXN],heavy[MAXN];

int hid[MAXN],hroot[MAXN],nh;
int hoff[MAXN+1],hsz[MAXN],hnode[MAXN];

TNode t[MAXN];
PTNode ht[MAXN];


void dfsinit(int at) {
	sz[at]=1; dep[at]=par[at]==-1?0:dep[par[at]]+1; heavy[at]=-1;
	REPSZ(i,ch[at]) {
		int to=ch[at][i];
		dfsinit(to);
		sz[at]+=sz[to];
		if(heavy[at]==-1||sz[to]>sz[heavy[at]]) heavy[at]=to;
	}
}

void dfsheavy(int at) {
	int h=nh++; ht[h]=NULL; hsz[h]=0;
	for(int x=at;x!=-1;x=heavy[x]) {
		hid[x]=h,hroot[x]=at,++hsz[h],hnode[hoff[h]+dep[x]-dep[hroot[x]]]=x;
		t[x].prio=rand(),t[x].sz=1,t[x].val=sval[x],t[x].l=t[x].r=NULL; PTNode tmp=ht[h]; merge(ht[h],tmp,&t[x]);
		//printf("added\n"); print(ht[h]); puts("");
	}
	hoff[nh]=hoff[h]+hsz[h];
	for(int x=at;x!=-1;x=heavy[x]) {
		REPSZ(i,ch[x]) {
			int to=ch[x][i]; if(to==heavy[x]) continue;
			dfsheavy(to);
		}
	}
}


int getval(int x) {
	//printf("getval(%d)\n",x);
	int h=hid[x],idx=dep[x]-dep[hroot[x]];
	PTNode l,m,r;
	split(ht[h],l,m,idx);
	split(m,m,r,1);
	int ret=m->val;
	merge(m,m,r);
	merge(ht[h],l,m);
	return ret;
}
void setval(int x,int v) {
	int h=hid[x],idx=dep[x]-dep[hroot[x]];
	PTNode l,m,r;
	split(ht[h],l,m,idx);
	split(m,m,r,1);
	m->val=v;
	merge(m,m,r);
	merge(ht[h],l,m);
}
void trotate(PTNode &x,int cnt) {
	PTNode l,m,r;
	split(x,l,r,cnt);
	split(l,l,m,1);
	merge(l,m,l);
	merge(x,l,r);
}

int ans[MAXQ],nans;
void rotate(int x) {
	assert(nans<MAXQ); ans[nans++]=x;
	int leafval=getval(0);
	while(x!=-1) {
		//printf("leafval=%d\n",leafval);
		int h=hid[x];
		int rootval=getval(hroot[x]);
		//printf("rootval=%d\n",rootval);
		trotate(ht[h],dep[x]-dep[hroot[x]]+1);
		setval(x,leafval);
		x=par[hroot[x]],leafval=rootval;
	}
}

int hcur[MAXN],hrem[MAXN],nhcur;
bool iscurnode[MAXN];
int curdeg[MAXN];
int q[MAXN],qhead,qtail;

int bit[MAXN+1];
void bmod(int idx,int by) { ++idx; while(idx<=n) { bit[idx]+=by; idx+=idx&-idx; } }
int bget(int idx) { ++idx; int ret=0; while(idx>0) { ret+=bit[idx]; idx-=idx&-idx; } return ret; }
int bgetrange(int lidx,int ridx) { return bget(ridx)-bget(lidx-1); }

void findcurrent(int at) {
	bool iscurrent=true;
	for(int x=at;x!=-1;x=heavy[x]) {
		REPSZ(i,ch[x]) {
			int to=ch[x][i]; if(to==heavy[x]) continue;
			if(hrem[hid[to]]!=0) iscurrent=false;
		}
	}
	if(iscurrent) {
		hcur[nhcur++]=hid[at];
		for(int x=at;x!=-1;x=heavy[x]) {
			if(heavy[x]!=-1) ++curdeg[x];
			if(curdeg[x]==0) q[qhead++]=x;
			iscurnode[x]=true;
		}
	} else {
		for(int x=at;x!=-1;x=heavy[x]) {
			if(heavy[x]!=-1) ++curdeg[x];
			REPSZ(i,ch[x]) {
				int to=ch[x][i]; if(to==heavy[x]||hrem[hid[to]]==0) continue;
				++curdeg[x];
				findcurrent(to);
			}
			if(curdeg[x]==0) q[qhead++]=x;
		}
	}
}

void process() {
	int tmpidx=0;
	//int rep=0;
	while(tmpidx<nhcur) {
		//if(++rep>20) exit(0);
		int val=getval(0);
		//printf("val=%d\n",val);
		if(iscurnode[val]) {
			int h=hid[val];
			int have=bgetrange(hoff[h]+dep[val]-dep[hroot[val]],hoff[h]+hsz[h]-1);
			int pos=hsz[h]-1-have;
			//printf("current rotate to %d (have=%d [%d..%d])\n",hnode[hoff[h]+pos],have,hoff[h]+dep[val]-dep[hroot[val]],hoff[h]+hsz[h]-1);
			rotate(hnode[hoff[h]+pos]);
			--hrem[h];
			bmod(hoff[h]+dep[val]-dep[hroot[val]],+1);
		} else {
			while(true) {
				assert(qtail<qhead);
				int at=q[qtail++];
				if(par[at]!=-1&&--curdeg[par[at]]==0) q[qhead++]=par[at];
				if(iscurnode[at]) {
					int h=hid[at];
					int have=hsz[h]-hrem[h];
					int pos=hsz[h]-have;
					//printf("!! at=%d have=%d pos=%d delta=%d\n",at,have,pos,dep[at]-dep[hroot[at]]);
					if(dep[at]-dep[hroot[at]]>=pos) continue;
				}
				//printf("rotate to %d\n",at);
				rotate(at);
				break;
			}
		}
		while(tmpidx<nhcur&&hrem[hcur[tmpidx]]==0) ++tmpidx;
	}
}

void solve() {
	REP(i,n) ch[i].clear(); REP(i,n) if(par[i]!=-1) ch[par[i]].PB(i);
	dfsinit(0);
	nh=0; hoff[0]=0; dfsheavy(0);

	//REP(i,n) printf("%d: sz=%d dep=%d heavy=%d hid=%d hroot=%d\n",i,sz[i],dep[i],heavy[i],hid[i],hroot[i]);
	//REP(i,nh) { printf("h%d:",i); print(ht[i]); puts(""); }

	//printf("val:"); REP(i,n) printf(" %d",getval(i)); puts("");

	REP(i,nh) hrem[i]=hsz[i]; nans=0; REPE(i,n) bit[i]=0;
	while(hrem[hid[0]]>0) {
		nhcur=0; REP(i,n) iscurnode[i]=false,curdeg[i]=0; qhead=qtail=0; findcurrent(0); if(nhcur==0) break;
		//printf("hcur:"); REP(i,nhcur) { int h=hcur[i]; REP(j,hsz[h]) printf("%c%d",j==0?' ':',',hnode[hoff[h]+j]); } puts("");
		//printf("deg:"); REP(i,n) printf(" %d",curdeg[i]); puts("");
		process();
	}
}

void run() {
	scanf("%d",&n); par[0]=-1; FOR(i,1,n) scanf("%d",&par[i]); REP(i,n) scanf("%d",&sval[i]);
	solve();
	printf("%d\n",nans); REP(i,nans) printf("%d\n",ans[i]);
}

void stress() {
	REP(rep,100) {
		n=MAXN; par[0]=-1; FOR(i,1,n) par[i]=rand()%i; REP(i,n) sval[i]=i; REP(i,n) { int idx=i+rand()%(n-i); swap(sval[i],sval[idx]); }
		//printf("%d\n",n); FOR(i,1,n) { if(i!=1) printf(" "); printf("%d",par[i]); } puts(""); REP(i,n) { if(i!=0) printf(" "); printf("%d",sval[i]); } puts("");
		solve();
		printf("nq=%d\n",nans);
	}
}

int main() {
	run();
	//stress();
	return 0;
}

```