#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define get are_connected
int find(vector<int> v,vector<int> v1)
{
int s=-1,e=v1.size()-1;
while (s+1<e)
{
int mid=(s+e)/2;
vector<int> c;
for (int i=0;i<=mid;i++) c.push_back(v1[i]);
if (get(v,c))
e=mid;
else
s=mid;
}
return e;
}
vector<int> merge(vector<int> &v1,vector<int> &v)
{
int x=find(v,v1);
int y=find({v1[x]},v);
vector<int> ans;
for (int i:v)
if (i!=v[y])
ans.push_back(i);
ans.push_back(v[y]);
for (int i=x;i<v1.size();i++)
ans.push_back(v1[i]);
return ans;
}
vector<int> longest_trip(int n, int D)
{
vector<int> cur={0};
bool vis[n]={};
while (cur.size()<n)
{
vis[cur.back()]=1;
vector<int> v;
for (int i=0;i<n;i++)
if (!vis[i]) v.push_back(i);
if (!get(cur,v))
{
if (cur.size()<v.size()) return v;
return cur;
}
cur.push_back(v[find(cur,v)]);
}
cur={0};
for (int i=0;i<n;i++) vis[i]=0;
while (cur.size()<n)
{
vis[cur.back()]=1;
vector<int> v;
for (int i=0;i<n;i++)
if (!vis[i])
v.push_back(i);
int x=v[find(cur,v)];
int a=find({x},cur);
reverse(cur.begin(),cur.end());
int b=find({x},cur);
if (a<b)
{
reverse(cur.begin(),cur.end());
b=a;
}
vector<int> nw={x};
for (int i=b;i<cur.size();i++)
nw.push_back(cur[i]);
for (int i=0;i<b;i++)
nw.push_back(cur[i]);
cur=nw;
}
return cur;
}
