#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int n, int D)
{
//Construct two chains
vector<int> path1 = {0}, path2;
bool tail_info = 0;
for(int i = 1; i < n; i++){
if(path2.size() == 0){
if(are_connected({path1.back()}, {i}) == 1) path1.push_back(i);
else path2.push_back(i);
}
else{
if(tail_info == 1){
if(are_connected({path1.back()}, {i}) == 1) path1.push_back(i);
else path2.push_back(i);
tail_info = 0;
}
else{
int x = are_connected({path1.back()}, {i});
if(x == 1){path1.push_back(i); continue;}
int y = are_connected({path2.back()}, {i});
if(y == 1){path2.push_back(i); tail_info = 1;}
else{
//The tail are connected
tail_info = (path2.size() == 1);
while(path2.size() > 0){
path1.push_back(path2.back()); path2.pop_back();
}
path2.push_back(i);
}
}
}
}
//Ok now we have two chain
if(path1.size() < path2.size()) swap(path1, path2);
if(path2.size() == 0) return path1;
if(path1.size() <= 2){
if(path2.size() == 1){
int x = are_connected({path1[0]}, {path2[0]});
int y = are_connected({path1[1]}, {path2[0]});
if(x == 0 && y == 0) return path1;
else if(x == 1) return {path1[1], path1[0], path2[0]};
else return {path1[0], path1[1], path2[0]};
}
bool x = 0, y = 0;
int ax = are_connected({path1[0]}, {path2[0]});
int ay = are_connected({path1[0]}, {path2[1]});
int bx = are_connected({path1[1]}, {path2[0]});
int by = are_connected({path1[1]}, {path2[1]});
if(ax == 1){x = 1; y = 0;}
else if(ay == 1){x = 1; y = 1;}
else if(bx == 1){x = 0; y = 0;}
else if(by == 1){x = 0; y = 1;}
else return path1;
if(x == 1) reverse(path1.begin(), path1.end());
if(y == 1) reverse(path2.begin(), path2.end());
for(int i : path2) path1.push_back(i);
return path1;
}
else{
if(are_connected({path1[0]}, {path2[0]}) == 1){
reverse(path1.begin(), path1.end());
for(int i : path2) path1.push_back(i);
return path1;
}
if(are_connected({path1.back()}, {path2[0]}) == 1){
for(int i : path2) path1.push_back(i);
return path1;
}
//Now we could binary search
if(are_connected(path1, path2) == 0) return path1;
//path1 is a cycle
int l = 0, r = path1.size()-1, p = -1;
while(l <= r){
int mid = (l+r)/2;
vector<int> question;
for(int i = 0; i <= mid; i++) question.push_back(path1[i]);
if(are_connected(question, {path2[0]}) == 1){p = mid; r = mid-1;}
else l = mid+1;
}
vector<int> ans;
for(int i = p+1; i < path1.size(); i++) ans.push_back(path1[i]);
for(int i = 0; i <= p; i++) ans.push_back(path1[i]);
for(int i : path2) ans.push_back(i);
return ans;
}
}
