#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
void split(vector<int>&v,int sz,vector<int>&a,vector<int>&b)
{
for(int i=0;i<sz;i++){
a.push_back(v[i]);
}
for(int i=sz;i<v.size();i++){
b.push_back(v[i]);
}
}
void BS(vector<int>A,vector<int>B,int&s,int&e)
{
while(A.size()>1){
vector<int>a,b;
split(A,(A.size())/2,a,b);
if(are_connected(a,B)){
swap(A,a);
}
else{
swap(A,b);
}
}
while(B.size()>1){
vector<int>a,b;
split(B,(B.size())/2,a,b);
if(are_connected(A,a)){
swap(B,a);
}
else{
swap(B,b);
}
}
s=A[0];
e=B[0];
}
std::vector<int> longest_trip(int N, int D)
{
vector<int>path(1);
vector<bool>vis(N);
vis[0]=true;
while(path.size()<N){
int a=path.front();
int b=path.back();
int c,d;
vector<int>rest;
for(int i=0;i<N;i++){
if(!vis[i]){
rest.push_back(i);
}
}
if(are_connected(vector<int>(1,a),rest)){
BS(vector<int>(1,a),rest,c,d);
path.insert(path.begin(),d);
vis[d]=true;
continue;
}
if(are_connected(vector<int>(1,b),rest)){
BS(vector<int>(1,b),rest,c,d);
path.push_back(d);
vis[d]=true;
continue;
}
if(!are_connected(path,rest)){
if(path.size()>=rest.size()){
return path;
}
return rest;
}
BS(path,rest,c,d);
for(int i=0;i<path.size();i++){
if(path[i]==c){
c=i;
break;
}
}
for(int i=0;i<rest.size();i++){
if(rest[i]==d){
d=i;
break;
}
}
vector<int>ans;
for(int i=c+1;i<path.size();i++){
ans.push_back(path[i]);
}
for(int i=0;i<=c;i++){
ans.push_back(path[i]);
}
for(int i=d;i<rest.size();i++){
ans.push_back(rest[i]);
}
for(int i=0;i<d;i++){
ans.push_back(rest[i]);
}
return ans;
}
return path;
}
