//將用邊表示的樹轉化為前序表示的樹
//傳入節點數n和鄰接表list[],鄰接表必須是雙向的,會在函數中釋放
//pre[]返回前序表,map[]返回前序表中的節點到原來節點的映射
#define MAXN 10000
struct node{
	int to;
	node* next;
};

void prenode(int n,node* list[],int* pre,int* map,int* v,int now,int last,int& id){
	node* t;
	int p=id++;
	for (v[map[p]=now]=1,pre[p]=last;list[now];){
		t=list[now],list[now]=t->next;
		if (!v[t->to])
			prenode(n,list,pre,map,v,t->to,p,id);
	}
}

void makepre(int n,node* list[],int* pre,int* map){
	int v[MAXN],id=0,i;
	for (i=0;i<n;v[i++]=0);
	prenode(n,list,pre,map,v,0,-1,id);
}