#include <bits/stdc++.h>
using namespace std;

int n, a, b, vis[100010], tp[100010];
vector<int> to[100010], ans, rs;

void DFS(int x, int pa) {
  if(vis[x]) {
    if(vis[x] == 1) {
      for(int i = tp[x]; i < ans.size(); i++) {
        rs.push_back(ans[i]);
      }
      sort(rs.begin(), rs.end());
      for(auto i : rs) {
        cout << i << ' ';
      }
      cout << '\n';
      exit(0);
    }
    return ;
  }
  vis[x] = 1;
  tp[x] = ans.size();
  ans.push_back(x);
  for(auto i : to[x]) {
    if(i != pa) {
      DFS(i, x);
    }
  }
  vis[x] = -1;
  tp[x] = -1;
  ans.pop_back();
}

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> a >> b;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  DFS(1, 0);
  return 0;
}

AC 记录

可以被如下的数据 hack：

5
1 2
2 3
3 4
4 5
1 2

正确输出：

1 2

上面错误程序的输出：

2

本题可没说保证新接边之后仍然是简单图，所以可以出现重边。