测试点 #2 过不去

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
typedef long long ll;
const ll N=2e6+5;
int t,n,m,fr[N],to[N],pa[N],dep[N],zhx[N],d[N],que[N],qr;
vector<int>v[N],g[N];
map<pair<int,int>,bool>mp;
void build(int x,int y){
	if(x>y) swap(x,y);
	mp[make_pair(x,y)]=1;
	printf("%d %d\n",x,y);
}
bool cmp(int x,int y){return zhx[x]<zhx[y];} 
void dfs1(int x){
	for(int i=0;i<v[x].size();i++){
		dep[v[x][i]]=dep[x]+1;
		dfs1(v[x][i]);
	}
}
void dfs(int x){
	sort(v[x].begin(),v[x].end(),cmp);
	for(int i=0;i<v[x].size();i++){
		build(x,v[x][i]);
		dfs(v[x][i]);
	}
}
int main(){
	srand(time(0));
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&fr[i],&to[i]);
		if(fr[i]>to[i]) swap(fr[i],to[i]);
	}
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x),pa[i]=x;
		v[x].push_back(i);
		if(i>1){
			g[i].push_back(x);
			d[x]++;
		}
	}
	dep[1]=1;dfs1(1);
	for(int i=1;i<=m;i++)
		if(abs(dep[fr[i]]-dep[to[i]])>1) puts("WTF!!!");
		else
			if(abs(dep[fr[i]]-dep[to[i]])==1)
				if(!(pa[fr[i]]==to[i]||pa[to[i]]==fr[i])){
					if(dep[fr[i]]>dep[to[i]]){
						g[fr[i]].push_back(to[i]);
						d[to[i]]++;
					}
					else{
						g[to[i]].push_back(fr[i]);
						d[fr[i]]++;
					}
				}
	for(int i=1;i<=n;i++)
		if(!d[i])
			que[zhx[i]=++qr]=i;
	for(int i=1,u;i<=qr;i++){
		u=que[i];
		for(int j=0;j<g[u].size();j++)
			if(!--d[g[u][j]])
				que[zhx[g[u][j]]=++qr]=g[u][j];
	}
	dfs(1);
	for(int i=1,x,y;i<=m;i++)
		if(mp[make_pair(fr[i],to[i])]) mp[make_pair(fr[i],to[i])]=0;
		else printf("%d %d\n",fr[i],to[i]);
	return 0;
}