#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
bool czy[300];
vector<int> longest_trip(int n, int d)
{
int i;
vector<int>tab[2];tab[0].push_back(0);tab[1].push_back(1);
for(i=1;i<n/2;i++){
int a = i*2, b = i*2+1;
if(are_connected({a}, {b})){
if(are_connected({a}, {tab[0].back()})){
tab[0].push_back(a);
tab[0].push_back(b);
}
else if(are_connected({a}, {tab[1].back()})){
tab[1].push_back(a);
tab[1].push_back(b);
}
else{
while(tab[1].size()){
tab[0].push_back(tab[1].back());
tab[1].pop_back();
}
tab[1].push_back(a);
tab[1].push_back(b);
}
}
else{
if(are_connected({a}, {tab[0].back()})){
tab[0].push_back(a);
if(are_connected({b}, {tab[1].back()}))
tab[1].push_back({b});
else{
while(tab[1].size()){
tab[0].push_back(tab[1].back());
tab[1].pop_back();
}
tab[1].push_back(b);
}
}
else{
tab[0].push_back(b);
if(are_connected({a}, {tab[1].back()}))
tab[1].push_back({a});
else{
while(tab[1].size()){
tab[0].push_back(tab[1].back());
tab[1].pop_back();
}
tab[1].push_back(a);
}
}
}
}
if(n%2){
if(are_connected({n-1}, {tab[0].back()}))
tab[0].push_back(n-1);
else if(are_connected({n-1}, {tab[1].back()}))
tab[1].push_back(n-1);
else{
while(tab[1].size()){
tab[0].push_back(tab[1].back());
tab[1].pop_back();
}
tab[1].push_back(n-1);
}
}
if(tab[0].size()>=tab[1].size())return tab[0];
return tab[1];
}
