#include "longesttrip.h"
#include <deque>
#include <algorithm>
std::vector<int> longest_trip(int N, int D)
{
std::vector<std::deque<int>> vec;
vec.push_back((std::deque<int>){0});
for (int i = 1; i < N; ++i)
{
if (vec.size() == 1)
{
std::deque<int> &vv = vec[0];
if (are_connected({vv[0]}, {i}))
vv.push_back(i);
else
vec.push_back((std::deque<int>){i});
}
else
{
int a = are_connected({vec[0][0]}, {vec[1][0]});
int b = are_connected({vec[0][0]}, {i});
int c = are_connected({vec[1][0]}, {i});
if (a)
{
std::reverse(vec[1].begin(), vec[1].end());
vec[0].insert(vec[0].begin(), vec[1].begin(), vec[1].end());
vec[1] = std::deque<int>{i};
}
else if (b)
{
vec[0].push_front(i);
}
else
{
vec[1].push_front(i);
}
}
}
std::vector<int> fres(vec[0].begin(), vec[0].end());
if (vec.size() > 1 && vec[1].size() > vec[0].size())
fres = std::vector<int>(vec[1].begin(), vec[1].end());
return fres;
}
