#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> longest_trip(int n, int d)
{
vector<vector<int>> v;
for(int i=0;i<n;i++)v.push_back({i});
while(v.size()>2){
vector<int> v1,v2,v3;
v1=v.back();v.pop_back();
v2=v.back();v.pop_back();
v3=v.back();v.pop_back();
if(are_connected({v1[0]},{v2[0]})){
reverse(v1.begin(),v1.end());
for(int i:v2)v1.push_back(i);
v.push_back(v1);
v.push_back(v3);
}else if(are_connected({v1[0]},{v3[0]})){
reverse(v1.begin(),v1.end());
for(int i:v3)v1.push_back(i);
v.push_back(v1);
v.push_back(v2);
}else{
reverse(v2.begin(),v2.end());
for(int i:v3)v2.push_back(i);
v.push_back(v2);
v.push_back(v1);
}
}
if(v[0].size()>v[1].size())swap(v[0],v[1]);
if(are_connected(v[0],v[1])){
if(are_connected({v[0][0]},{v[1][0]})){
reverse(v[0].begin(),v[0].end());
for(int i:v[1])v[0].push_back(i);
return v[0];
}else if(are_connected({v[0][0]},{v[1].back()})){
for(int i:v[0])v[1].push_back(i);
return v[1];
}else if(are_connected({v[0].back()},{v[1][0]})){
for(int i:v[1])v[0].push_back(i);
return v[0];
}else if(are_connected({v[0].back()},{v[1].back()})){
reverse(v[0].begin(),v[0].end());
for(int i:v[0])v[1].push_back(i);
return v[1];
}else{
for(int i=0;i<v[0].size();i++){
for(int j=0;j<v[1].size();j++){
if(are_connected({v[0][i]},{v[1][j]})){
vector<int> ans;
for(int x=i+1;x<v[0].size();x++)ans.push_back(v[0][x]);
for(int x=0;x<=i;x++)ans.push_back(v[0][x]);
for(int x=j;x<v[1].size();x++)ans.push_back(v[1][x]);
for(int x=0;x<j;x++)ans.push_back(v[1][x]);
return ans;
}
}
}
}
}
return v[1];
}
