#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> f(int x,vector<int> v){
if(v.empty())return {x};
int idx=rng();
idx=abs(idx)%v.size();
vector<int> v1,v2;
for(int i=0;i<v.size();i++)if(i!=idx){
if(are_connected({v[idx]},{v[i]}))v1.push_back(v[i]);
else v2.push_back(v[i]);
}
v1=f(v[idx],v1);
v1.push_back(x);
for(int i:v2)v1.push_back(i);
return v1;
}
std::vector<int> longest_trip(int n, int d)
{
vector<int> v1,v2;
int idx=rng();
idx=abs(idx)%n;
for(int i=0;i<n;i++)if(i!=idx){
if(are_connected({idx},{i}))v1.push_back(i);
else v2.push_back(i);
}
v1=f(idx,v1);
if(v2.empty())return v1;
bool b1=are_connected({v1[0]},v2),b2=are_connected({v1.back()},v2);
if(b1)reverse(v1.begin(),v1.end());
if(b1||b2){
for(int i:v2){
if(are_connected({v1.back()},{i})){
v1.push_back(i);
for(int j:v2)if(i!=j)v1.push_back(j);
return v1;
}
}
}else if(are_connected(v1,v2)){
for(int i=0;i<v1.size();i++)if(are_connected({v1[i]},v2)){
for(int j:v2){
if(are_connected({v1[i]},{j})){
vector<int> ans;
for(int k=i+1;k<v1.size();k++)ans.push_back(v1[k]);
for(int k=0;k<=i;k++)ans.push_back(v1[k]);
ans.push_back(j);
for(int k:v2)if(j!=k)ans.push_back(k);
return ans;
}
}
}
}
if(v1.size()>v2.size())return v1;
return v2;
}
