#include "longesttrip.h"
#include <stack>
using namespace std;
#define pb push_back
vector<int> longest_trip(int n, int d){
vector<int> ans;
if(d==3){
for(int i=0; i<n; i++){
ans.pb(i);
}
} else if(d==2){
// surely there still exists a round trip...
// why is this screaming linked list :(
bool has_split=0;
stack<int> cur;
for(int i=0; i<n-1; i++){
cur.push(i);
if(!are_connected({i}, {i+1})){
if(i>0)has_split=true;
while(!cur.empty()){
ans.pb(cur.top());
cur.pop();
}
}
}
if(!has_split)ans.pb(n-1);
while(!cur.empty()){
ans.pb(cur.top());
cur.pop();
}
if(has_split)ans.pb(n-1);
}
return ans;
}
