#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int n, int d) {
vector<int> ans = { 1 };
set<int> st;
for(int i=2; 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;
}
}
return ans;
}
