#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int N, int D) {
vector<int> trip1(1, 0), trip2;
for (int i = 1; i < N; i++) {
bool b = are_connected(vector<int>(1, trip1.front()), vector<int>(1, i)),
b2 = are_connected(vector<int>(1, trip1.back()), vector<int>(1, i));
if (!b && !b2)
trip2.push_back(i);
else if (trip2.empty()) {
if (b)
trip1.insert(trip1.begin(), i);
else
trip2.push_back(i);
} else if (b) {
bool b3 = are_connected(vector<int>(1, trip2.front()), vector<int>(1, i)),
b4 = are_connected(vector<int>(1, trip2.back()), vector<int>(1, i));
if (b3) {
trip1.insert(trip1.begin(), i);
for (auto a : trip2) trip1.insert(trip1.begin(), a);
trip2.clear();
} else if (b4) {
trip2.push_back(i);
for (auto a : trip1) trip2.push_back(a);
trip1 = trip2;
trip2.clear();
} else {
trip1.insert(trip1.begin(), i);
}
} else if (b2) {
bool b3 = are_connected(vector<int>(1, trip2.front()), vector<int>(1, i)),
b4 = are_connected(vector<int>(1, trip2.back()), vector<int>(1, i));
if (b3) {
trip1.push_back(i);
for (auto a : trip2) trip1.push_back(a);
trip2.clear();
} else if (b4) {
reverse(trip2.begin(), trip2.end());
trip1.push_back(i);
for (auto a : trip2) trip1.push_back(a);
trip2.clear();
} else {
trip1.push_back(i);
}
}
}
if (trip1.size() < trip2.size()) trip1.swap(trip2);
return trip1;
}
