问题标题: 酷町堂：阶段考试第3题

现在有一棵n个结点的树，在这棵树上又选取了两点，本来两点之间没有边，现在给它们之间增加了一条边。如果把这棵树看成是一个图，于是在这个图上产生了一个环。现在希望删掉一对点组成的边，使得这个图变回一棵树，请求出应该删掉哪一对点组成的边。
如果有多种删除方案，输出输入中最靠后的那一对边。（即树中产生了一个环，把环的最后一条输入的边给输出出来）

输入描述 Input Description
第一行，一个整数n，表示加了一条边后图中的边数
接下来n行，每行两个整数,a b，表示点a和点b之间存在一对边

输出描述 Output Description
两个空格隔开的整数，表示最后一个删掉之后变为树的那一对边，小的点在前，大的点在后

样例输入 Sample Input
3
1 2
1 3
2 3
样例输出 Sample Output
2 3

阶段考试的时候状态不好，导致这道水题20分，我先说下我的思路：

一开始的反应是欧拉路径，输出起点和终点等输入顺序靠后的结点编号。

然后第二种思路是按将输入顺序逆序删边（实时清空出度、入度），然后每删一条边就用欧拉回路判环，如果是环就输出2个点的编号，数据存储看n<=20就用邻接链表存储的，时间O(n²)左右，自己手造了几组数据、样例过了（老师说思路不对）

包括这个图：（哈密尔顿回路会卡的）

具体实现代码：

#include <iostream>
#include <cstring>
#define MAXN 1005
using namespace std;
int n,m,g[MAXN][MAXN],st,ed,s,u[MAXN],v[MAXN];
int path[MAXN],len,du[MAXN];
bool dfs(int x) 
{
    for(int i=1;i<=n;i++)
    {
        if(g[x][i])
        {
            g[x][i]=g[i][x]=0;
            dfs(i); 
        } 
    }
    path[++len]=x;
}
int main() 
{
    cin>>n;
    for(int i=1;i<=n;i++) 
    {
        cin>>u[i]>>v[i];
        du[u[i]]++;
        du[v[i]]++;
        g[u[i]][v[i]]=g[v[i]][u[i]]=1;
    }
    for(int i=n;i>=1;i--)
    {
        du[u[i]]--;
        du[v[i]]--;
        g[u[i]][v[i]]=g[v[i]][u[i]]=0;
        for(int j=1;j<=n;j++)
            if(du[j]%2==1)
            {
                s=j;
                break;
            }
        dfs(s);
        if(path[1]!=path[n])
        {
            cout<<min(v[i],u[i])<<" "<<max(u[i],v[i]);
            break;
        }
        s=0;
        len=0;
        memset(path,0,sizeof(path));
        du[u[i]]++;
        du[v[i]]++;
        g[u[i]][v[i]]=g[v[i]][u[i]]=1;
    }
}

大家帮我看下为什么WA 20分

大家的思路是什么？或者谁能给出卡掉我算法的数据？谢谢