#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(0);
std::vector<int> longest_trip(int N, int D)
{
vector<int>x,y;
x.push_back(0);
for(int i=1;i<N;i++){
if(are_connected({0}, {i})){
x.push_back(i);
} else{
y.push_back(i);
}
}
if(y.size()>0 && !are_connected(x,y)){
if(x.size()>y.size()){
return x;
} else{
return y;
}
}
if(y.empty()){
vector<int>ans;
vector<int>p;
ans.push_back({1});
for(int i=2;i<N;i++){
p.push_back(i);
}
while(!p.empty()){
shuffle(p.begin(),p.end(),rng);
if(!are_connected({ans.back()}, p)){
break;
}
for(int i: p){
if(are_connected({ans.back()}, {i})){
ans.push_back(i);
p.erase(find(p.begin(),p.end(), i));
break;
}
}
}
ans.push_back(0);
for(int i: p){
ans.push_back(i);
}
return ans;
}
vector<int>y_;
for(int i=0;i<N;i++){
if(find(y.begin(),y.end(),i)==y.end()){
y_.push_back(i);
}
}
int lo=0;
int hi=y.size()-1;
while(lo<hi){
int m=(lo+hi)/2;
vector<int>vv;
for(int i=lo;i<=m;i++){
vv.push_back(y[i]);
}
if(are_connected(vv, y_)){
hi=m;
} else{
lo=m+1;
}
}
swap(y[y.size()-1], y[lo]);
vector<int>ans=y;
vector<int>p;
for(int i=1;i<N;i++){
if(find(y.begin(),y.end(),i)==y.end()){
p.push_back(i);
}
}
while(!p.empty()){
shuffle(p.begin(),p.end(),rng);
if(!are_connected({ans.back()}, p)){
break;
}
for(int i: p){
if(are_connected({ans.back()}, {i})){
ans.push_back(i);
p.erase(find(p.begin(),p.end(), i));
break;
}
}
}
ans.push_back(0);
for(int i: p){
ans.push_back(i);
}
return ans;
}
