树中的每个节点都有一个父节点，除了根节点没有父节点。在多了一条附加的边之后，可能有以下两种情况：

1. 附加的边指向根节点，则包括根节点在内的每个节点都有一个父节点，此时图中一定有环路；

2. 附加的边指向非根节点，则恰好有一个节点（即被附加的边指向的节点）有两个父节点，此时图中可能有环路也可能没有环路。

要找到附加的边，需要遍历图中的所有的边构建出一棵树，在构建树的过程中寻找导致冲突（即导致一个节点有两个父节点）的边以及导致环路出现的边。

具体做法是，使用数组$parent$记录每个节点的父节点，初始时对于任何$1≤i≤n$都有$parent[i]=i$，另外创建并查集，初始时并查集中的每个节点都是一个连通分支，该连通分支的根节点就是该节点本身。遍历每条边的过程中，维护导致冲突的边和导致环路出现的边，由于只有一条附加的边，因此最多有一条导致冲突的边和一条导致环路出现的边。

当访问到边 [u,v] 时，进行如下操作

1. 如果此时已经有$parent[v] != v$，说明 v 有两个父节点，将当前的边 [u,v] 记为导致冲突的边；

2. 否则，令$parent[v]=u$，然后在并查集中分别找到 u 和 v 的祖先（即各自的连通分支中的根节点），如果祖先相同，说明这条边导致环路出现，将当前的边 [u,v] 记为导致环路出现的边，如果祖先不同，则在并查集中将 u 和 v 进行合并。

根据上述操作，同一条边不可能同时被记为导致冲突的边和导致环路出现的边。如果访问到的边确实同时导致冲突和环路出现，则这条边被记为导致冲突的边。

在遍历图中的所有边之后，根据是否存在导致冲突的边和导致环路出现的边，得到附加的边。

1. 如果没有导致冲突的边，说明附加的边一定导致环路出现，而且是在环路中的最后一条被访问到的边，因此附加的边即为导致环路出现的边。

2. 如果有导致冲突的边，记这条边为 [u,v]，则有两条边指向 v，另一条边为 [parent[v],v]，需要通过判断是否有导致环路的边决定哪条边是附加的边。

3. 如果有导致环路的边，则附加的边不可能是 [u,v]（因为 [u,v] 已经被记为导致冲突的边，不可能被记为导致环路出现的边），因此附加的边是 [parent[v],v]。

4. 如果没有导致环路的边，则附加的边是后被访问到的指向 v 的边，因此附加的边是 [u,v]。

时间复杂度：$O(nlogn)$，其中$n$是图中的节点个数。需要遍历图中的$n$条边，对于每条边，需要对两个节点查找祖先，如果两个节点的祖先不同则需要进行合并，需要进行 2 次查找和最多 1 次合并。一共需要进行$2n$次查找和最多$n$次合并，因此总时间复杂度是$O(2nlogn)=O(nlogn)$。这里的并查集使用了路径压缩，但是没有使用按秩合并，最坏情况下的时间复杂度是$O(nlogn)$，平均情况下的时间复杂度依然是$O(nα(n))$，其中$α$为阿克曼函数的反函数，$α(n)$可以认为是一个很小的常数。

空间复杂度：$O(n)$，其中$n$是图中的节点个数。使用数组$parent$记录每个节点的祖先。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
class unionFind
{
    vector<int> fa;
public:
    unionFind(int len) {
        fa.resize(len + 1);
        for (int i = 1; i <= len; i++)
            fa[i] = i;
    }
    int find(int x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }
    void merge(int x, int y) {
        fa[find(y)] = find(x);
    }
};
int main()
{
    int n, x, y;
    cin >> n;
    vector<int> parent(n + 1, 0), conflict, circle;
    unionFind uf(n);
    for (int i = 1; i <= n; i++)
        parent[i] = i;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y;
        if (parent[y] != y)
            conflict = vector<int>{x, y};
        else {
            parent[y] = x;
            if (uf.find(x) == uf.find(y))
                circle = vector<int>{x, y};
            else
                uf.merge(x, y);
        }
    }
    if (conflict.empty())
        cout << circle[0] << " " << circle[1];
    else if (circle.empty())
        cout << conflict[0] << " " << conflict[1];
    else
        cout << parent[conflict[1]] << " " << conflict[1];
    return 0;
}