思路大概就是记录一下一条边是否为树边，通过找LCA确定优先级，然后输出答案。

但是不知道为什么会一直WA on #2

My code :

#include <bits/stdc++.h>
using namespace std;
#define  debug(_)  std::cout << "it is ok " << (_) << std::endl
#define int long long
inline int read(){
    int x = 0; int f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = 0; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    return f ? x : -x;
}
inline void write(int x){
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
const int N = 2e6;
std::vector<int> graph[N];
std::pair<int, int> g[N];
std::queue<int> q;
std::bitset<N> st, vis;
std::pair<int, int> G[N], g2[N];
int n, m, result[N];
int dep[N], fa[N][32], pa[N];
int size[N], son[N], id, length;
int isit[N], sta[N], top;
inline void dfs(int u, int ff)
{
    dep[u] = dep[ff] + 1;
    fa[u][0] = ff;
    for(int i = 1; i <= 30; ++ i )
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (auto v : graph[u])
    {
        if (v == ff) continue;
        dfs(v, u);
    }
}
inline void lca(int x, int y){
    if(x == y) return;
    if(dep[x] < dep[y]) std::swap(x, y);
    int t = dep[x] - dep[y];
    for(int i = 30; i >= 0; -- i )
        if(t >= 1 << i){
            t -= 1 << i;
            x = fa[x][i];
        }
    if(x == y) return;
    for(int i = 30; i >= 0; -- i )
        if(fa[x][i] ^ fa[y][i]){
            x = fa[x][i];
            y = fa[y][i];
        }
    
    pa[y] = x;
}
void Work(int u, int ff)
{
    for (auto v : graph[u]) {
        if (v == ff) continue;
        int o = v; top = 0;
        if (isit[v] ^ u) sta[ ++ top] = v; 
        while(pa[v]){
            if (isit[pa[v]]) break;
            v = pa[v];
            sta[++top] = v;
        }
        while(top){
            write(sta[top]), putchar(32), write(u), putchar(10);
            isit[sta[top--]] = u;
        }
        Work(o, u);
    }
}
bool cmp(pair<int, int> &a, pair<int, int> &b) {
    if (a.first != b.first) return a.first < b.first;
    return a.second <= b.second;
}
signed main()
{
    n = read(), m = read();
    for (int i = 1; i <= m; i ++ ) {
        int u, v; u = read(), v = read();
        if (u > v) std::swap(u, v);
        g2[i] = std::make_pair(u, v);
    }
    std::sort(g2 + 1, g2 + m + 1, cmp);
    g[ ++ length] = g2[1];
    for (int i = 2; i <= m; i ++ ) {
        if (g2[i] == g2[i - 1] || g2[i] == make_pair(g2[i - 1].second, g2[i - 1].second)) {
            G[ ++ id] = g2[i];
            continue;
        } else 
            g[ ++ length] =  g2[i];
    }
    for (int i = 1; i <= n; i ++ )
        result[i] = read();
    for (int i = 2; i <= n; i ++ ) {
        graph[i].push_back(result[i]), graph[result[i]].push_back(i);
        int it = std::lower_bound(g + 1, g + length + 1, std::make_pair(std::min(i, result[i]), std::max(i, result[i]))) - g;
        vis[it] = true;
    }
    dfs(1, 0);
    for (int i = 1; i <= length; i ++ )
        if (!vis[i])
        {
            lca(g[i].first, g[i].second);
            G[ ++ id] = g[i];
        }
    Work(1, 1);
    for (int i = 1; i <= id; i ++ )
        write(G[i].first), putchar(32), write(G[i].second), putchar(10);
    return 0;
}