#include "longesttrip.h"
#include <queue>
#include <iostream>
#include <assert.h>
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);
}
}
if(d==1){
// the boss fight
vector<int> link(n, -1);
int start1, start2, end1, end2;
int a,b,c;
queue<int> q;
a=are_connected({0}, {1});
b=are_connected({1}, {2});
c=are_connected({0}, {2});
if(a){
start1=0;
link[0]=1;
end1=1;
} else if(b){
start1=1;
link[1]=2;
end1=2;
} else if(c){
start1=0;
link[0]=2;
end1=2;
}
for(int i=0; i<n; i++){
if(i!=start1 && i!=end1){
q.push(i);
}
}
a=-1;b=-1;c=-1;
start2=-1;end2=-1;
while(!q.empty()){
// a
a=end1;
// b
if(start2==-1){
b=q.front();
q.pop();
start2=b;
end2=b;
}
// c
if(c==-1){
c=q.front();
q.pop();
}
//cerr<<"#(a,b,c)"<<a<<","<<b<<","<<c<<"\n";
//assert(a!=b);
//assert(b!=c);
//assert(a!=c);
if(are_connected({a}, {b})){
// a-b (join the lists)
link[a]=b;
end1=end2;
start2=-1;
end2=-1;
} else if(are_connected({a}, {c})){
// a-c (go to list1)
end1=c;
link[a]=c;
c=-1;
} else if(1==1 || are_connected({b}, {c})){
// b-c (go to list2)
start2=c;
link[c]=b;
c=-1;
}
}
int cur=start1;
int siz=1;
vector<int> ans1={start1};
while(link[cur] != -1){
cur = link[cur];
ans1.pb(cur);
}
if(start2==-1){
return ans1;
} // else...
cur=start2;
vector<int> ans2={start2};
while(link[cur] != -1){
cur = link[cur];
ans2.pb(cur);
}
if(ans1.size() >= ans2.size()){
return ans1;
} else{
return ans2;
}
}
return ans;
}
