我只有 90pts，是 #2 WA了,考的时候改了无数遍也没过。

大概说一下我自己的思路，如果有哪里不对的还请大家矫正。

因为给出来了这个最后的序列，通过最后的序列建边，可以得到一棵树。这样可以把一开始输入给我们的边分为树边和非树边。。根据这个遍历的顺序，然后我就lca搞了一下优先级。然后把这些树边按一定顺序输出，最后输出的那些没有用的非树边。

但是真的不知道为什么会WA on #2.打的时候以为是没有判断重边的问题。但似乎又不是。

真的一头雾水。

（上面的是我的思路，不算是讨论区发题解，违规紫衫）

这是我的代码：

#include <bits/stdc++.h>
using namespace std;
#define  debug(_)  std::cout << "fuck" << (_) << 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][31], 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 <= 25; ++ 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 = 25; i >= 0; -- i )
        if(t >= 1 << i){
            t -= 1 << i;
            x = fa[x][i];
        }
    if(x == y) return;
    for(int i = 25; i >= 0; -- i )
        if(fa[x][i] ^ fa[y][i]){
            x = fa[x][i];
            y = fa[y][i];
        }
    
    pa[y] = x;
}

void Go(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;
        }
        Go(o, u);
    }
}
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);

    g[ ++ length] = g2[1];
    for (int i = 2; i <= m; i ++ ) {
        if (g2[i] == g2[i - 1]) {
            G[ ++ id] = g2[i];
            continue;
        }
        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, 1);

    for (int i = 1; i <= length; i ++ )
        if (!vis[i])
        {
            lca(g[i].first, g[i].second);
            G[ ++ id] = g[i];
        }

    Go(1, 1);

    for (int i = 1; i <= id; i ++ )
        write(G[i].first), putchar(32), write(G[i].second), putchar(10);
    return 0;
}