我的思路如下

先广搜分层

然后每一层排先后顺序

最后再广搜输出

代码如下

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+20; 
int n,m,a[N],vis[N];
vector<int> ma[N];
int b[N],sy; 
int deg[N],cnto[N],imp[N];
bool cmp(int x,int y) {return deg[x]>deg[y];};
bool cmp2(int x,int y) {return imp[x]<imp[y];};
vector<int> build[N];
vector<int> ms[N];
void dfs(int u,int fa)
{
	if(u==1||vis[u]) return;
	vis[u]=1;
	for(int i=0;i<ma[u].size();i++)
	{
		int v=ma[u][i];
		if(v==fa) continue;
		else if(v==a[u]) continue;
		else if(deg[u]>deg[v]) {
			cnto[a[u]]++;
			build[v].push_back(a[u]);
		}
	}
	dfs(a[u],u);
}
void dfs2(int u,int fa)
{
	if(vis[u]) return;
	vis[u]=1;
	for(int i=0;i<build[u].size();i++)
	{
		int v=build[u][i];
		if(v==fa) continue;
		dfs2(v,u);
	}
	ms[deg[u]].push_back(u);
}
void bfs()
{
	queue<int> q;
	q.push(1);
    b[1]=1,deg[1]=1;
	while(!q.empty())
	{
		int u = q.front();
        q.pop();
        for (int i=0;i<ma[u].size();i++)
        {
        	int v=ma[u][i];
            if (deg[v])continue;
            b[v]=v,deg[v]=deg[u]+1;
            q.push(v);
        }
	}
}
int L[N],R[N],rt[N];
void fen()
{
	int l=1,r=1,root=0;
	cnto[0]=2e9;
	while(r<=n)
	{
		sy++;
		while(r<=n&&deg[b[l]]==deg[b[r]]) 
		{
			if(cnto[b[r]]<cnto[root]) root=b[r];
			r++;
		}
		L[sy]=l;
		R[sy]=r-1;
		rt[sy]=root;
		l=r;
		root=0;
	}
}
void bfs2()
{
	queue<int> q;
	q.push(1);
    vis[1]=1;
	while(!q.empty())
	{
		int u = q.front();
        q.pop();
        sort(ma[u].begin(),ma[u].end(),cmp2);
        for (int i=0;i<ma[u].size();i++)
        {
        	int v=ma[u][i];
        	if(deg[v]>deg[u]) cout << u << ' ' << v << endl;
            if (vis[v]) continue;
            vis[v]=1;
            q.push(v);
        }
	}
}
int main()
{
	cin >> n >> m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin >> x >> y;
		ma[x].push_back(y);
		ma[y].push_back(x);
	}
	bfs();
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=n;i++) if(!vis[b[i]]) dfs(b[i],-1);
	fen();
	for(int i=1;i<=n;i++) vis[i]=0;
	for(int i=1;i<=sy;i++) dfs2(rt[i],-1);
	for(int i=1;i<=sy;i++) for(int j=0;j<ms[i].size();j++) imp[ms[i][j]]=j+1;
//	cout << endl;
//	for(int i=1;i<=n;i++) cout << b[i] << ' ' << deg[b[i]] << ' ' << cnto[b[i]] << endl;
//	cout << endl;
//	for(int i=1;i<=sy;i++) cout << L[i] << ' ' << R[i] << ' ' << rt[i] << endl;
	for(int i=1;i<=n;i++) vis[i]=0;
	bfs2();
//	for(int i=0;i<mus.size();i++) cout << mus[i].deg << ' ' << mus[i].index << endl;
//	for(int i=0;i<fw.size();i++) cout << fw[i].deg << ' ' << fw[i].index << endl;
	return 0;
}