#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
std::vector<int> longest_trip(int n, int D) {
vi ans;
vvi adj(n, vi(n));
for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++) adj[i][j] = adj[j][i] = are_connected({i}, {j});
vi seen(n);
auto dfs = [&](auto dfs, int u) -> void {
if (seen[u]) return;
seen[u] = 1;
ans.push_back(u);
for (int v = 0; v < n; v++) if (adj[v][u]) dfs(dfs, v);
};
dfs(dfs, 0);
if (ans.size() != n) {
if (ans.size() > n-ans.size()) return ans;
for (int i = 0; i < n; i++) if (!seen[i]) {
ans.clear();
dfs(dfs, i);
return ans;
}
}
for (int i = 0; i < n; i++) {
if (accumulate(adj[i].begin(), adj[i].end(), 0) == 1) {
ans.clear();
seen = vi(n);
dfs(dfs, i);
break;
}
}
return ans;
}
