#include "longesttrip.h"
#include <queue>
using namespace std;
#define pb push_back
vector<int> longest_trip(int n, int d){
vector<int> ans;
if(d==2){
// surely there still exists a round trip...
// why is this screaming linked list :(
vector<int> starts;
if(!are_connected({0}, {n-1})){
starts.pb(0);
}
for(int i=1; i<n; i++){
if(!are_connected({i-1}, {i})){
starts.pb(i);
}
}
if(starts.size()==0){
d=3; // go do the easy case (0,1,2,...)
} else{
// we certainly have breaks somewhere.
starts.pb(starts[0]+n);
bool forwards=false;
for(int j=0; j<starts.size()-1; j++){
forwards = !forwards;
if(forwards){
// forwards
for(int i=starts[j]; i<starts[j+1]; i++){
ans.pb(i%n);
}
} else{
// backwards
for(int i=starts[j+1]-1; i>starts[j]-1; i--){
ans.pb(i%n);
}
}
}
}
}
if(d==3){
for(int i=0; i<n; i++){
ans.pb(i);
}
}
return ans;
}
