#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int>vrni(vector<int>&v,int r)
{
vector<int>temp;
for(int i=0;i<=r;i++)temp.push_back(v[i]);
return temp;
}
vector<int> longest_trip(int N, int D)
{
n=N;
int k1=0;
vector<int>v1,v2;
v1.push_back(0);
v2.push_back(1);
for(int i=2;i<n;i++)
{
if(k1==0)
{
if(are_connected({v1.back()},{i}))
{
v1.push_back(i);
}
else if(are_connected({v2.back()},{i}))
{
v2.push_back(i);
k1=2;
}
else
{
while(!v2.empty())
{
v1.push_back(v2.back());
v2.pop_back();
}
v2.push_back(i);
}
}
else if(k1==2)
{
if(are_connected({v1.back()},{i}))
{
v1.push_back(i);
k1=0;
}
else
{
v2.push_back(i);
}
}
}
if(!are_connected(v1,v2))
{
if(v1.size()>v2.size())return v1;
return v2;
}
if(are_connected({v1.back()},{v2[0]}))
{
for(int i=0;i<v2.size();i++)
{
v1.push_back(v2[i]);
}
return v1;
}
else if(are_connected({v1.back()},{v2.back()}))
{
for(int i=v2.size()-1;i>=0;i--)
{
v1.push_back(v2[i]);
}
return v1;
}
else if(are_connected({v1[0]},{v2[0]}))
{
reverse(v1.begin(),v1.end());
for(int i=0;i<v2.size();i++)
{
v1.push_back(v2[i]);
}
return v1;
}
else if(are_connected({v1[0]},{v2.back()}))
{
reverse(v1.begin(),v1.end());
for(int i=v2.size()-1;i>=0;i--)
{
v1.push_back(v2[i]);
}
return v1;
}
else
{
int l=0,r=v1.size()-1;
while(r>l)
{
int m=(l+r)/2;
vector<int>temp=vrni(v1,m);
if(are_connected(temp,v2))r=m;
else l=m+1;
}
int k=l;
l=0,r=v2.size()-1;
while(r>l)
{
int m=(l+r)/2;
vector<int>temp=vrni(v2,m);
if(are_connected(temp,{v1[k]}))r=m;
else l=m+1;
}
vector<int>res;
int i=(k+1)%v1.size();
while(i!=k)
{
res.push_back(v1[i]);
i=(i+1)%v1.size();
}
res.push_back(v1[k]);
k=l;
res.push_back(v2[k]);
i=(k+1)%v2.size();
while(i!=k)
{
res.push_back(v2[i]);
i=(i+1)%v2.size();
}
return res;
}
}
