#include "longesttrip.h"
#include <bits/stdc++.h>
template<typename T>
using vec = std::vector<T>;
using namespace std;
std::vector<int> longest_trip(int N, int D)
{
vec<int> nodes(N); for (int i = 0; i < N; i++) nodes[i] = i;
if (D == 3)
return nodes;
if (D == 2) {
deque<int> path{0, are_connected({0}, {1}) ? 1 : 2};
nodes.erase(find(nodes.begin(), nodes.end(), path.front()));
nodes.erase(find(nodes.begin(), nodes.end(), path.back()));
while (!nodes.empty()) {
auto u = nodes.back(); nodes.pop_back();
if (are_connected({path.front()}, {u}))
path.push_front(u);
else
path.push_back(u);
}
return vec<int>(path.begin(), path.end());
}
list<int> path[2] = {{0}, {1}};
nodes.erase(find(nodes.begin(), nodes.end(), path[0].back()));
nodes.erase(find(nodes.begin(), nodes.end(), path[1].back()));
while (!nodes.empty()) {
auto u = nodes.back(); nodes.pop_back();
if (are_connected({path[0].back()}, {u}))
path[0].push_back(u);
else if (are_connected({path[1].back()}, {u}))
path[1].push_back(u);
else {
auto &small = path[0], &large = path[1];
if (small.size() > large.size()) swap(small, large);
small.reverse();
large.splice(large.end(), small);
path[0] = large;
path[1] = {u};
}
}
return path[0].size() > path[1].size() ? vec<int>(path[0].begin(), path[1].end()) : vec<int>(path[1].begin(), path[1].end());
}
