我的思路跟大部分人一样，也是对于每条边的先后限制建有向图，然后按拓扑序输出。

然后 WA #1#2，经过 assert 发现拓扑排序以后还是有点的入度不为 $0$，也就是说出现了环，此时无解，但题目保证有解，不知道代码哪里写丑了，求调或者 hack，实在是改不动了。

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb emplace_back
#define push emplace
#define mkp make_pair
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using ull=unsigned long long;
bool Mbe;
inline void read(int &x){
  char ch=getchar();
  int r=0,w=1;
  while(!isdigit(ch))w=ch=='-'?-1:1,ch=getchar();
  while(isdigit(ch))r=(r<<1)+(r<<3)+(ch^48),ch=getchar();
  x=r*w;
}
const int N=2e5+7;
map<pii,int>mp;
vector<int>edge[N],e[N];
int n,m,x[N],y[N];
int f[N][18],dep[N],in[N],faid[N];
bool ok[N];
void dfs(int u,int fa){
  dep[u]=dep[fa]+1;
  f[u][0]=fa;
  for(int i=1;i<=17;i++)f[u][i]=f[f[u][i-1]][i-1];
  for(int v:edge[u])dfs(v,u);
}
void lca(int u,int v){
  if(dep[u]<dep[v])swap(u,v);
  for(int i=17;i>=0;i--)if(dep[f[u][i]]>=dep[v])u=f[u][i];
  for(int i=17;i>=0;i--)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
  e[faid[u]].pb(faid[v]);in[faid[v]]++;
}
queue<int>q;
void topsort(){
  for(int i=1;i<=m;i++)if(ok[i]&&!in[i])q.push(i);
  while(!q.empty()){
    int u=q.front();q.pop();
    printf("%d %d\n",x[u],y[u]);
    for(int v:e[u])if(--in[v]==0)q.push(v);
  }
  for(int i=1;i<=m;i++)if(ok[i])assert(!in[i]);
  for(int i=1;i<=m;i++)if(!ok[i])printf("%d %d\n",x[i],y[i]);
}
void solve(){
  read(n);read(m);
  for(int i=1;i<=m;i++){
    read(x[i]),read(y[i]);
    mp[mkp(x[i],y[i])]=i;
    mp[mkp(y[i],x[i])]=i;
  }
  for(int i=1,x;i<=n;i++){
    read(x);
    if(i==1)continue;
    faid[i]=mp[mkp(x,i)];
    ok[mp[mkp(x,i)]]=1;
    if(x!=0)edge[x].pb(i);
  }
  dfs(1,0);
  for(int i=1;i<=m;i++)
    if(!ok[i]&&dep[x[i]]!=dep[y[i]])lca(x[i],y[i]);
  topsort();
}

bool Med;
int main(){
  fprintf(stderr,"%.3lf MB\n",(&Med-&Mbe)/1048576.0);
  int T=1;
  while(T--)solve();
  cerr<<1e3*clock()/CLOCKS_PER_SEC<<" ms\n";
  return 0;
}