#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<bool> vis;
int nadji (const vector<int> & c,const vector<int>& v){
int sz=v.size();
if(sz==0)return -1;
if(!are_connected(c,v))return -1;
int l=0;
int r=sz-1;
vector<int> pom;
while(l<r){
int mid=l+(r-l)/2;
pom.clear();
for(int i=l;i<=mid;i++)pom.push_back(v[i]);
if(are_connected(c,pom))r=mid;
else l=mid+1;
}
return v[l];
}
vector<int> longest_trip(int N, int D)
{
n=N;
vector<int> s1;
vector<int> s2;
s1.push_back(0);
for(int i=1;i<n;i++){
bool con=are_connected({0},{i});
if(con)s1.push_back(i);
else s2.push_back(i);
}
if(s2.size()!=0 && !are_connected(s1,s2)){
if(s2.size()>s1.size())return s2;
return s1;
}
int c1=0;
int c2=s1[1];
vis.assign(n,false);
vis[0]=true;
vis[c2]=true;
bool promena=false;
deque<int> dq;
dq.push_back(c1);
dq.push_back(c2);
vector<int> pom;
while(true){
pom.clear();
for(int i=0;i<n;i++){
if(!vis[i])pom.push_back(i);
}
if(!promena){
int x=nadji({dq.back()},pom);
if(x==-1)promena=true;
else{
dq.push_back(x);
vis[x]=true;
}
}
if(promena){
int x=nadji({dq.front()},pom);
if(x==-1)break;
dq.push_front(x);
vis[x]=true;
}
}
pom.clear();
for(int i=0;i<n;i++)if(!vis[i])pom.push_back(i);
vector<int> v;
while(dq.size()!=0){
v.push_back(dq.back());
dq.pop_back();
}
if(pom.size()==0)return v;
int poc=-1;
int kraj=-1;
poc=nadji(pom,v);
kraj=nadji({poc},pom);
int pos=-1;
vector<int> ans;
for(int i=0;i<v.size();i++)if(v[i]==poc)pos=i;
for(int i=0;i<v.size();i++)ans.push_back(v[(pos+i+1)%(v.size())]);
ans.push_back(kraj);
for(int i=0;i<pom.size();i++)if(pom[i]!=kraj)ans.push_back(pom[i]);
return ans;
}
