#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
vector<bool> vis;
vector<vector<int>> adj,g;
vector<int> d,F;
int mx,idx;
void dfs(int u){
vis[u]=1;
for(int x:adj[u]){
if(vis[x]) continue;
g[u].push_back(x);
g[x].push_back(u);
dfs(x);
}
}
void DFS(int u,int p=-1){
if(d[u]>mx) mx=d[u],idx=u;
for(int x:g[u]){
if(x==p) continue;
d[x]=d[u]+1;
F[x]=u;
DFS(x,u);
}
}
vector<int> TR(int x,int st){
vector<int> ret;
int now=x;
while(now!=st){
ret.push_back(now);
now=F[now];
}
ret.push_back(st);
return ret;
}
vector<int> longest_trip(int N, int D){
adj.resize(N);
vis.resize(N);
g.resize(N);
d.resize(N);
F.resize(N);
for(int i=0;i<N;i++){
for(int j=i+1;j<N;j++){
bool x=are_connected({i},{j});
if(x) adj[i].push_back(j),adj[j].push_back(i);
}
}
vector<int> ret;
for(int i=0;i<N;i++){
if(vis[i]) continue;
dfs(i);
d[i]=1;
mx=0;
DFS(i);
if(mx>ret.size()) ret=TR(idx,i);
int tidx=idx;
mx=0;
for(int i=0;i<N;i++) d[i]=0;
d[idx]=1;
DFS(idx);
if(mx>ret.size()) ret=TR(idx,tidx);
for(int j=0;j<N;j++) g[j].clear();
}
adj.clear();
vis.clear();
g.clear();
d.clear();
F.clear();
return ret;
}
