#include "longesttrip.h"
#include "bits/stdc++.h"
using namespace std;
#define vi vector<int>
#define ii pair<int,int>
const int mxn=257;
vector<int> adj[mxn];
ii dfs(int u, vector<bool> &vis, vi &res, bool sw){
vis[u]=true;
ii best={0,u};
int nxt=u;
for(int v: adj[u]){
if(vis[v]) continue;
ii act=dfs(v,vis,res,sw);
if(act.first+1>best.first) best={act.first+1,act.second},nxt=v;
}
if(sw && nxt!=u) res.push_back(nxt);
return best;
}
vi longest_trip(int n, int d){
for(int i=0;i<n;i++) adj[i].clear();
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(are_connected({i},{j}))
adj[i].push_back(j),adj[j].push_back(i);
vector<bool> first(n,false),second(n,false);
vector<int> res;
for(int i=0;i<n;i++){
if(first[i]) continue;
vi act;
int st=dfs(i,first,act,false).second;
dfs(st,second,act,true);
act.push_back(st);
if(act.size()>res.size()) res=act;
}
return res;
}
