#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
mt19937 rng(time(0));
bool edge(int i,int j){return are_connected({i},{j});}
vector<int>longest_trip(int n,int D){
vector<int>path={0},path1;
bool notconnected=true;
for(int i=1;i<n;i++){
if(notconnected){
if(!path.empty()&&edge(path.back(),i))path.pb(i);
else path1.pb(i);
notconnected=false;
continue;
}
if(rng()%2==0){
if(!path.empty()&&edge(path.back(),i))path.pb(i);
else if(!path1.empty()&&edge(path1.back(),i))path1.pb(i),notconnected=true;
else{
while(!path1.empty())path.pb(path1.back()),path1.pop_back();
path1.pb(i);
}
}
else{
if(!path1.empty()&&edge(path1.back(),i))path1.pb(i);
else if(!path.empty()&&edge(path.back(),i))path.pb(i),notconnected=true;
else{
while(!path1.empty())path.pb(path1.back()),path1.pop_back();
path1.pb(i);
}
}
}
if(path.size()<path1.size())swap(path,path1);
if(!path.empty()&&!path1.empty()&&are_connected(path,path1)){
if(edge(path[0],path1[0])){
reverse(path.begin(),path.end());
for(auto i:path1)path.pb(i);
return path;
}
if(edge(path[0],path1.back())){
for(auto i:path)path1.pb(i);
return path1;
}
if(edge(path.back(),path1[0])){
for(auto i:path1)path.pb(i);
return path;
}
if(edge(path.back(),path1.back())){
reverse(path1.begin(),path1.end());
for(auto i:path1)path.pb(i);
return path;
}
int l=0,r=(int)path.size()-1,ind=-1;
while(l<=r){
int mid=l+r>>1;
vector<int>temp;
for(int i=0;i<=mid;i++)temp.pb(path[i]);
if(are_connected(temp,path1))ind=mid,r=mid-1;
else l=mid+1;
}
l=0,r=(int)path1.size()-1;int j=-1;
while(l<=r){
int mid=l+r>>1;
vector<int>temp;
for(int i=0;i<=mid;i++)temp.pb(path1[i]);
if(are_connected({path[ind]},temp))j=mid,r=mid-1;
else l=mid+1;
}
vector<int>temp;
for(int i=ind+1;i<path.size();i++)temp.pb(path[i]);
for(int i=0;i<=ind;i++)temp.pb(path[i]);
path=temp;
temp.clear();
for(int i=j+1;i<path1.size();i++)temp.pb(path1[i]);
for(int i=0;i<=j;i++)temp.pb(path1[i]);
path1=temp;
reverse(path1.begin(),path1.end());
for(auto i:path1)path.pb(i);
}
return path;
}
