#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
vector<int> longest_trip(int n, int D){
vector<vector<bool>> d(n, vector<bool>(n));
vector<int> g[n];
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
d[i][j] = d[j][i] = are_connected({i}, {j});
if (d[i][j]){
g[i].pb(j);
g[j].pb(i);
}
}
}
vector<int> c;
queue<int> q;
vector<bool> used(n);
vector<int> F;
for (int i = 0; i < n; i++){
if (used[i]) continue;
q.push(i); used[i] = 1; c.clear();
while (!q.empty()){
int v = q.front(); q.pop();
c.pb(v);
for (int j: g[v]){
if (!used[j]){
q.push(j);
used[j] = 1;
}
}
}
if (c.size() > F.size()){
F = c;
}
}
vector<int> out;
vector<bool> ban(n);
for (int i: F){
for (int j: F){
if (d[i][j]){
out.pb(i);
out.pb(j);
ban[i] = ban[j] = 1;
break;
}
}
if (!out.empty()) break;
}
if (F.size() <= 2) return F;
for (int i: F){
if (ban[i]) continue;
if (d[out[0]][i]){
out.insert(out.begin(), i);
ban[i] = 1;
continue;
}
}
for (int i: F){
if (ban[i]) continue;
if (d[out.back()][i]){
out.pb(i);
ban[i] = 1;
continue;
}
}
while (out.size() != F.size()){
bool I = 0;
for (int i: F){
if (ban[i]) continue;
if (d[i][out[0]]){
out.insert(out.begin(), i);
ban[i] = 1;
I = 1;
break;
}
if (d[i][out.back()]){
out.pb(i);
ban[i] = 1;
I = 1;
break;
}
}
if (I) continue;
assert(d[out[0]][out.back()]);
for (int i = 1; i + 1 < out.size(); i++){
for (int j: F){
if (ban[j]) continue;
if (d[out[i]][j]){
vector<int> nw;
nw.pb(j);
for (int k = i ; k < out.size(); k++){
nw.pb(out[k]);
}
for (int k = 0; k < i; k++){
nw.pb(out[k]);
}
out = nw;
I = 1;
ban[j] = 1;
break;
}
}
if (I) break;
}
}
return out;
}
