#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> best;
void dfs(vector<vector<int>> &adjacency, vector<bool> &visited, vector<int> &seq, int cur) {
visited[cur] = true;
bool last = true;
seq.push_back(cur);
for (auto &child : adjacency[cur]) {
if (visited[child]) continue;
last = false;
dfs(adjacency, visited, seq, child);
}
if (last && seq.size() > best.size()) {
best.clear();
for (int &i : seq) best.push_back(i);
}
seq.pop_back();
}
std::vector<int> longest_trip(int N, int D)
{
best.clear();
vector<vector<int>> adjacency(N);
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
if (are_connected(vector<int>{i}, vector<int>{j})) adjacency[i].push_back(j), adjacency[j].push_back(i);
}
}
for (int i = 0; i < N; ++i) {
vector<bool> visited(N, false);
vector<int> seq;
dfs(adjacency, visited, seq, i);
}
return best;
}
