#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int N, int D) {
vector<vector<int>> g(N);
vector<deque<int>> comp(N);
for (int i = 0; i < N; i++)
comp[i].push_back(i);
while (comp.size() > 2) {
int i = 0;
int j = 1;
int k = 2;
int u = comp[i].back();
int v = comp[j].back();
int w = comp[k].back();
if (are_connected({v}, {w})) {
swap(u, w);
swap(i, k);
} else if (are_connected({u}, {w})) {
swap(v, w);
swap(j, k);
}
g[u].push_back(v);
g[v].push_back(u);
reverse(comp[j].begin(), comp[j].end());
comp[i].insert(comp[i].end(), comp[j].begin(), comp[j].end());
comp.erase(comp.begin() + j);
}
if (comp[0].size() < comp[1].size()) {
swap(comp[0], comp[1]);
}
return vector<int>(comp[0].begin(), comp[0].end());
}
