#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> v;
vector<int> used;
vector<int> now, res;
void dfs(int x) {
now.push_back(x);
used[x] = 1;
if (now.size() > res.size())
res = now;
for (auto to : v[x]) {
if (used[to])
continue;
dfs(to);
}
used[x] = 0;
now.pop_back();
}
vector<int> longest_trip(int N, int D) {
if (D == 3) {
vector<int> t(N);
iota(t.begin(), t.end(), 0);
return t;
}
v.clear();
used.resize(N);
v.resize(N);
now.clear();
res.clear();
fill(used.begin(), used.end(), 0);
for (int i = 1; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (are_connected({i}, {j})) {
v[i].push_back(j);
v[j].push_back(i);
}
}
}
for (int i = 0; i < N; i++) {
dfs(i);
}
return res;
}
