#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
static mt19937 g(42);
vector<int> longest_trip(int n, int d)
{
if(d==3)
{
vector<int> res(n);
iota(res.begin(),res.end(),0);
return res;
}
vector<int> nodes(n);
iota(nodes.begin(),nodes.end(),0);
shuffle(nodes.begin(),nodes.end(),g);
vector<int> a={nodes[0]};
vector<int> b={nodes[1]};
bool last=true;
for(int i=2; i<n; i++)
{
int v=nodes[i];
if(last)
{
if(are_connected({v},{a.back()}))
{
a.push_back(v);
}
else if(are_connected({v},{b.back()}))
{
b.push_back(v);
last=false;
}
else
{
reverse(b.begin(),b.end());
a.insert(a.end(),b.begin(),b.end());
b={v};
last=false;
}
}
else
{
if(are_connected({v},{b.back()}))
{
b.push_back(v);
}
else if(are_connected({v},{a.back()}))
{
a.push_back(v);
last=true;
}
else
{
reverse(a.begin(),a.end());
b.insert(b.end(),a.begin(),a.end());
a={v};
last=true;
}
}
}
if(are_connected({a.back()},{b[0]}))
{
a.insert(a.end(),b.begin(),b.end());
return a;
}
if(are_connected({a.back()},{b.back()}))
{
reverse(b.begin(),b.end());
a.insert(a.end(),b.begin(),b.end());
return a;
}
if(are_connected({a[0]},{b[0]}))
{
reverse(a.begin(),a.end());
a.insert(a.end(),b.begin(),b.end());
return a;
}
if(are_connected({a[0]},{b.back()}))
{
b.insert(b.end(),a.begin(),a.end());
return b;
}
if(!are_connected(a,b))
{
return (a.size()>=b.size()) ? a : b;
}
int l=0;
int r=a.size()-1;
int aa=0;
while(l<=r)
{
int mid=(l+r)/2;
vector<int> sa(a.begin(),a.begin()+mid+1);
if(are_connected(sa,b))
{
aa=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
int l2=0;
int r2=b.size()-1;
int ab=0;
while(l2<=r2)
{
int mid=(l2+r2)/2;
vector<int> sb(b.begin(),b.begin()+mid+1);
if(are_connected({a[aa]},sb))
{
ab=mid;
r2=mid-1;
}
else
{
l2=mid+1;
}
}
vector<int> res;
int sza=a.size();
int szb=b.size();
for(int k=0; k<sza; k++)
{
res.push_back(a[(aa+1+k)%sza]);
}
for(int k=0; k<szb; k++)
{
res.push_back(b[(ab-k+szb)%szb]);
}
return res;
}
