#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> f(int x,vector<int> v){
if(v.empty())return {x};
vector<int> v1,v2;
for(int i=1;i<v.size();i++){
if(are_connected({v[0]},{v[i]}))v1.push_back(v[i]);
else v2.push_back(v[i]);
}
v1=f(v[0],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;
for(int i=1;i<n;i++){
if(are_connected({0},{i}))v1.push_back(i);
else v2.push_back(i);
}
v1=f(0,v1);
if(v1.size()>v2.size())return v1;
return v2;
}
