1

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int read(){
	int w=0,h=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
	while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
	return w*h;
}
struct Edge{int next,to;}edge[N];
int n,m,ret[N],deg[N],ID[N],dfn;
pair<int,int>e[N];
int head[N],num;
vector<int>H[N];
vector<pair<int,int>>G[N];
void add(int u,int v){edge[++num]=(Edge){head[u],v};head[u]=num;}
void Add(int u,int v){H[u].emplace_back(v);deg[v]++;}
namespace Tree{
	struct Node{int dep,fa,siz,son,top;}t[N];
	void dfs1(int u,int fa){
		t[u].dep=t[t[u].fa=fa].dep+(t[u].siz=1);
		for(auto[v,id]:G[u])
			if(v==fa){ret[u]=id;break;}
		for(int i=head[u],v;i;i=edge[i].next)
			if((v=edge[i].to)!=fa){
				dfs1(v,u);
				t[u].siz+=t[v].siz;
				if(t[v].siz>t[t[u].son].siz)t[u].son=v;
			}
	}
	void dfs2(int u,int topf){
		t[u].top=topf;
		if(t[u].son)dfs2(t[u].son,topf);
		for(int i=head[u],v;i;i=edge[i].next)
			if((v=edge[i].to)!=t[u].fa&&v!=t[u].son)dfs2(v,v);
	}
	int LCA(int x,int y){
		int fx=t[x].top,fy=t[y].top;
		while(fx!=fy){
			if(t[fx].dep<t[fy].dep)swap(fx,fy),swap(x,y);
			x=t[fx].fa;fx=t[x].top;
		}
		if(t[x].dep>t[y].dep)swap(x,y);
		return x;
	}
	int Approach(int x,int y){
		int fx=t[x].top,fy=t[y].top,pre=x;
		while(fx!=fy)x=t[pre=fx].fa,fx=t[x].top;
		return x==y?pre:t[y].son;
	}
}
using namespace Tree;
void dfs(int u,int fa){
	for(auto[v,id]:G[u])
		if(id!=ret[u]&&v!=fa&&t[fa].dep==t[v].dep){
			int lca=LCA(fa,v),tpx=Approach(u,lca),tpy=Approach(v,lca);
//			cout<<u<<' '<<v<<' '<<lca<<' '<<tpx<<' '<<tpy<<endl;
//			cout<<ret[tpx]<<' '<<ret[tpy]<<endl;
			Add(ret[tpx],ret[tpy]);
		}
//	cout<<"!"<<u<<' '<<ret[u]<<endl;
	for(int i=head[u],v;i;i=edge[i].next)
		if((v=edge[i].to)!=fa)dfs(v,u);
}
signed main(){
	n=read();m=read();
	for(int i=1,u,v;i<=m;i++){
		u=read();v=read();e[i]=make_pair(u,v);
		G[u].emplace_back(v,i);G[v].emplace_back(u,i);
	}
	for(int i=1;i<=n;i++)add(read(),i);
	dfs1(1,0);dfs2(1,1);dfs(1,0);queue<int>q;
	for(int i=1;i<=m;i++)if(!deg[i])q.push(i);
	while(!q.empty()){
		int u=q.front();q.pop();ID[++dfn]=u;
		for(auto v:H[u])
			if(--deg[v]==0)q.push(v);
	}
	for(int i=1;i<=dfn;i++)printf("%d %d\n",e[ID[i]].first,e[ID[i]].second);
	return 0;
}