#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
bool are_connected(vector<int> A, vector<int> B);
vector<int> connect(vector<int> a, vector<int> b) {
reverse(a.begin(), a.end());
for (auto x: b) a.push_back(x);
return a;
}
vector<int> longest_trip(int n, int d) {
vector<vector<int>> paths = {{0}, {1}, {2}};
for (int i = 3; i < n; i++) {
bool flag = 1;
for (int k: {0, 1, 2}) {
if (are_connected({paths[k].back()}, {i})) {
paths[k].push_back(i);
flag = 0;
break;
}
}
if (flag) {
vector<int> pathA, pathB;
if (are_connected({paths[0][0]}, {paths[1][0]})) {
pathA = connect(paths[0], paths[1]);
pathB = paths[2];
} else if (are_connected({paths[0][0]}, {paths[2][0]})) {
pathA = connect(paths[0], paths[2]);
pathB = paths[1];
} else {
pathA = connect(paths[2], paths[1]);
pathB = paths[0];
}
paths[0] = pathA;
paths[1] = pathB;
paths[2] = {i};
}
}
vector<int> pathA, pathB;
if (are_connected({0}, {1})) {
pathA = connect(paths[0], paths[1]);
pathB = paths[2];
} else if (are_connected({0}, {2})) {
pathA = connect(paths[0], paths[2]);
pathB = paths[1];
} else {
pathA = connect(paths[2], paths[1]);
pathB = paths[0];
}
if (pathA.size() > pathB.size()) return pathA;
return pathB;
}
