#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
std::vector<int> longest_trip(int n, int d)
{
vector<vector<int>> v;
for(int i=0;i<n;i++)v.push_back({i});
shuffle(v.begin(),v.end(),rng);
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();
vector<vector<int>> vv={v1,v2,v3};
shuffle(vv.begin(),vv.end(),rng);
v1=vv[0],v2=vv[1],v3=vv[2];
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{
int l=0,r=v[0].size()-1;
while(l<r){
int m=(l+r)/2;
vector<int> t;
for(int i=0;i<=m;i++)t.push_back(v[0][i]);
if(are_connected(t,v[1]))r=m;
else l=m+1;
}
int i=l;
l=0,r=v[1].size()-1;
while(l<r){
int m=(l+r)/2;
vector<int> t;
for(int i=0;i<=m;i++)t.push_back(v[1][i]);
if(are_connected(t,{v[0][i]}))r=m;
else l=m+1;
}
int j=l;
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];
}
