#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300;
vector<int> g[MAXN];
int pr[MAXN], dep[MAXN];
void dfs(int v) {
for (int u : g[v]) {
if (dep[u] != -1) continue;
dep[u] = dep[v] + 1;
pr[u] = v;
dfs(u);
}
}
vector<int> longest_trip(int N, int D) {
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
if (are_connected({i}, {j})) {
g[i].push_back(j);
g[j].push_back(i);
}
}
}
vector<int> ord(N);
int ans = 0;
for (int i = 0; i < N; ++i) {
fill(dep, dep + N, -1);
dep[i] = 0;
dfs(i);
for (int j = 0; j < N; ++j) {
if (dep[j] > ans) {
ord.clear();
ans = dep[j];
int u = j;
while (true) {
ord.push_back(u);
if (u == i) break;
u = pr[u];
}
}
}
}
fill(g, g + N, vector<int>());
return {ord};
}
