#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int n, int d) {
vector<int> ans = { 0 };
set<int> st;
for(int i=1; i<n; i++) st.insert(i);
while(st.size() >= 2) {
int u = *st.begin(); st.erase(u);
int v = *st.begin(); st.erase(v);
if(are_connected({ ans.back() }, { u }))
ans.push_back(u);
else
ans.push_back(v);
if(ans.back() == u) st.insert(v);
if(ans.back() == v) st.insert(u);
}
if(st.size() == 1) {
int u = *st.begin();
if(are_connected({ ans.back() }, { u })) {
ans.push_back(u);
} else if(are_connected({ 1 }, { u })) {
vector<int> ans2 = { u };
for(int x : ans) ans2.push_back(x);
ans = ans2;
} else {
for(int i=0; i+1<ans.size(); i++) {
if(are_connected({ ans[i] }, { u}) && are_connected({ u }, { ans[i+1] })) {
vector<int> ans2;
for(int j=0; j<=i; j++) ans2.push_back(ans[j]);
ans2.push_back(u);
for(int j=i+1; j<ans.size(); j++) ans2.push_back(ans[j]);
ans = ans2;
}
}
}
}
return ans;
}
