#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
// #define get are_connected
const int M = 256;
bool edg[M][M];
bool get(vector<int> v,vector<int> v1)
{
for (int i:v)
for (int j:v1)
if (edg[i][j]) return 1;
return 0;
}
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)
{
for (int i=0;i<n;i++)
for (int j=i+1;j<n;j++)
edg[i][j]=edg[j][i]=are_connected({i},{j});
bool vis[n]={};
vector<int> cur={0};vis[0]=1;
while (cur.size()<n)
{
vector<int> v;
for (int i=0;i<n;i++)
if (!vis[i]) v.push_back(i);
if (!get({cur.back()},v)) break;
int s=-1,e=v.size()-1;
while (s+1<e)
{
int mid=(s+e)/2;
vector<int> v1;
for (int i=0;i<=mid;i++)
v1.push_back(v[i]);
if (get({cur.back()},v1))
e=mid;
else
s=mid;
}
cur.push_back(v[e]),vis[v[e]]=1;
}
vector<vector<int>> pot;
pot.push_back(cur);
vector<int> v;
for (int i=0;i<n;i++)
if (!vis[i]) v.push_back(i);
pot.push_back(v);
if (v.size() && get(cur,v))
{
pot.push_back(merge(cur,v));
reverse(cur.begin(),cur.end());
pot.push_back(merge(cur,v));
}
vector<int> ans;
for (auto v:pot)
if (v.size()>ans.size()) ans=v;
return ans;
}
