#include "longesttrip.h"
#include <deque>
int center(int x, int y, int z)
{
if (are_connected(std::vector<int>{x}, std::vector<int>{y}) && are_connected(std::vector<int>{x}, std::vector<int>{z}))
return x;
if (are_connected(std::vector<int>{y}, std::vector<int>{x}) && are_connected(std::vector<int>{y}, std::vector<int>{z}))
return y;
if (are_connected(std::vector<int>{z}, std::vector<int>{x}) && are_connected(std::vector<int>{z}, std::vector<int>{y}))
return z;
int xq = are_connected(std::vector<int>{x}, std::vector<int>{y});
int yq = are_connected(std::vector<int>{x}, std::vector<int>{z});
int zq = are_connected(std::vector<int>{y}, std::vector<int>{z});
if (xq && yq) return x;
if (xq && zq) return y;
if (yq && zq) return z;
return -1;
}
std::vector<int> longest_trip(int N, int D)
{
std::deque<int> umm;
int cn = center(0, 1, 2);
if (cn == 0)
umm.insert(umm.end(), {1, 0, 2});
else if (cn == 1)
umm.insert(umm.end(), {0, 1, 2});
else if (cn == 2)
umm.insert(umm.end(), {0, 2, 1});
for (int i = 3; i < N; ++i)
{
int cnt = center(umm.back(), umm.front(), i);
if (cnt == i)
umm.push_front(i);
else if (cnt == umm.front())
umm.push_front(i);
else if (cnt == umm.back())
umm.push_back(i);
}
std::vector<int> fres;
for (int i = 0; i < umm.size(); ++i)
fres.push_back(umm[i]);
return fres;
}
