#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int n,d;
vector<int>getslice(int l,int r,deque<int>&v){
vector<int>res;
for(int i=l;i<=r;i++){
res.pb(v[i]);
}
return res;
}
vector<int>longest_trip(int N,int D){
n=N,d=D;
deque<int>trip1,trip2;
trip1.pb(0);
for(int i=1;i<n;i++){
bool ok=are_connected({trip1.back()},{i});
if(ok){
trip1.pb(i);
}else if(!trip2.size()){
trip2.pb(i);
}else{
ok=are_connected({trip2.back()},{i});
if(ok){
trip2.pb(i);
}else{
while(trip2.size()){
trip1.pb(trip2.back());
trip2.pop_back();
}
trip2.pb(i);
}
}
}
if(!trip2.size())return vector<int>(trip1.begin(),trip1.end());
if(!are_connected(vector<int>(trip1.begin(),trip1.end()),vector<int>(trip2.begin(),trip2.end()))){
if(trip1.size()<trip2.size())swap(trip1,trip2);
return vector<int>(trip1.begin(),trip1.end());
}
if(are_connected({trip1.front()},{trip2.front()})){
vector<int>ans;
for(int i=trip1.size()-1;0<=i;i--){
ans.pb(trip1[i]);
}
for(int i:trip2){
ans.pb(i);
}
return ans;
}
if(are_connected({trip1.back()},{trip2.front()})){
vector<int>ans;
for(int i:trip1){
ans.pb(i);
}
for(int i:trip2){
ans.pb(i);
}
return ans;
}
if(are_connected({trip1.back()},{trip2.back()})){
vector<int>ans;
for(int i:trip1){
ans.pb(i);
}
for(int i=trip2.size()-1;0<=i;i--){
ans.pb(trip2[i]);
}
return ans;
}
int ans1=0;
{
int l=1,r=trip1.size()-1;
while(l<=r){
int mid=(l+r)>>1;
bool ok=are_connected(getslice(l,mid,trip1),vector<int>(trip2.begin(),trip2.end()));
if(ok){
ans1=mid;
r=mid-1;
}else{
l=mid+1;
}
}
}
int ans2=0;
{
int l=1,r=trip2.size()-1;
while(l<=r){
int mid=(l+r)>>1;
bool ok=are_connected(getslice(l,mid,trip2),{trip1[ans1]});
if(ok){
ans2=mid;
r=mid-1;
}else{
l=mid+1;
}
}
}
vector<int>ans;
for(int i=ans1+1;i<trip1.size();i++){
ans.pb(trip1[i]);
}
for(int i=0;i<=ans1;i++){
ans.pb(trip1[i]);
}
for(int i=ans2;i<trip2.size();i++){
ans.pb(trip2[i]);
}
for(int i=0;i<ans2;i++){
ans.pb(trip2[i]);
}
return ans;
}
