#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
void get_distances(int u, int n, vvi &adj, vi &dist, vi &par) {
dist.assign(n, 0);
par.assign(n, -1);
queue<int> q;
vector<bool> seen(n, false);
seen[u] = true;
q.push(u);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto v : adj[cur]) {
if (seen[v]) continue;
seen[v] = true;
dist[v] = 1 + dist[cur];
par[v] = cur;
q.push(v);
}
}
}
vi longest_trip(int N, int D) {
int n = N, d = D;
if (d >= 2) {
vi ans(n); iota(ans.begin(), ans.end(), 0);
return ans;
}
vvi adj(n, vi());
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
bool edge = are_connected(vi({i}), vi({j}));
if (!edge) continue;
adj[i].push_back(j);
adj[j].push_back(i);
}
}
int bd = -1; vi best;
for (int i = 0; i < n; i++) {
vi dist, par;
get_distances(i, n, adj, dist, par);
int furthest = 0; for (int j = 1; j < n; j++) if (dist[j] > dist[furthest]) furthest = j;
int length = dist[furthest];
if (length <= bd) continue;
vi ans;
while (furthest != -1) {
ans.push_back(furthest);
furthest = par[furthest];
}
bd = length;
best = ans;
}
return best;
}
