#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int con[400][400],vis[401];
int n;
vector<int> compute(){
deque <int> curr,lft;
vector <int> ans;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(vis[i]==0&&vis[j]==0&&con[i][j]==1&&curr.size()==0){
curr.push_back(i);
curr.push_back(j);
vis[i]=vis[j]=1;
}
}
}
for(int i=0;i<n;i++){
if(vis[i]==0){
lft.push_back(i);
}
}
while(!lft.empty()){
int k=lft.size(),flag=0;
while(k--){
int k2=curr.size(),flag2=0;
while(k2--){
if(con[curr.back()][lft.front()]==1){
flag=flag2=1;
curr.push_back(lft.front());
vis[lft.front()]=1;
lft.pop_front();
break;
}
if(con[curr.front()][lft.front()]==1){
flag=flag2=1;
curr.push_front(lft.front());
vis[lft.front()]=1;
lft.pop_front();
break;
}
curr.push_front(curr.back());
curr.pop_back();
}
if(flag2==1) break;
lft.push_back(lft.front());
lft.pop_front();
}
if(flag==0) break;
}
for(int i:curr) ans.push_back(i);
return ans;
}
vector<int> longest_trip(int N, int D)
{
n=N;
memset(vis,0,sizeof vis);
memset(con,0,sizeof con);
for(int i=0;i<N;i++){
for(int j=i+1;j<N;j++) con[i][j]=con[j][i]=are_connected({i},{j});
}
vector <int> v1=compute(),v2=compute();
if(v1.size()>=v2.size()) return v1;
else return v2;
}
