#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int N, int D)
{
vector<int> a, b;
deque<int> d;
if(are_connected({0}, {1}))
{
d.push_back(0);
d.push_back(1);
} else {
d.push_back(0);
d.push_back(2);
}
for(int i = 0; i < N; i++)
{
if(find(d.begin(), d.end(), i) != d.end())
continue;
if(are_connected({i}, {d.back()}))
d.push_back(i);
else
d.push_front(i);
}
return vector(d.begin(), d.end());
/*a.push_back(0);
b.push_back(1);
for(int i = 2; i < N; i++)
{
bool ac = are_connected({i}, {a.back()}), bc = are_connected({i}, {b.back()});
if(ac)
{
a.push_back(i);
} else if(bc)
{
b.push_back(i);
} else {
for(int j = b.size() - 1; j >= 0; j--)
a.push_back(b[j]);
b.clear();
b.push_back(i);
}
}*/
if(a.size() > b.size())
return a;
return b;
}
