#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 256;
void append(vector<int> &a, vector<int> &b) {
for (int i : b) a.push_back(i);
}
vector<int> longest_trip(int N, int D) {
vector<vector<int>> paths;
for (int i = 2; i < N;) {
if (paths.size() == 0) {
bool b01 = are_connected({0}, {1});
bool b02 = are_connected({0}, {2});
bool b12 = are_connected({1}, {2});
if (b01 && b12) paths.push_back({0, 1, 2});
else if (b02 && b12) paths.push_back({0, 2, 1});
else if (b01 && b02) paths.push_back({1, 0 ,2});
else if (b01) paths.push_back({0, 1}), paths.push_back({2});
else if (b02) paths.push_back({0, 2}), paths.push_back({1});
else paths.push_back({1, 2}), paths.push_back({0});
i++;
} else if (paths.size() == 1) {
if (i == N-1) {
if (are_connected({paths[0].back()}, {i})) paths[0].push_back(i);
else if (are_connected({paths[0][0]}, {i})) paths[0].insert(paths[0].begin(), i);
else paths.push_back({i});
i++;
} else {
bool passed = false;
if (are_connected({paths[0].back()}, {i})) paths[0].push_back(i), passed = true;
else if (are_connected({paths[0][0]}, {i})) paths[0].insert(paths[0].begin(), i), passed = true;
i++;
if (passed) continue;
if (are_connected({paths[0].back()}, {i})) {
paths[0].push_back(i), passed = true;
if (are_connected({i-1}, {i})) paths[0].push_back(i-1);
else paths.push_back({i-1});
}
else if (are_connected({paths[0][0]}, {i})) {
paths[0].insert(paths[0].begin(), i), passed = true;
if (are_connected({i-1}, {i})) paths[0].insert(paths[0].begin(), i-1);
else paths.push_back({i-1});
}
i++;
if (passed) continue;
paths.push_back({i-2, i-1});
}
} else if (paths.size() == 2) {
if (are_connected({paths[0].back()}, {paths[1].back()})) {
reverse(paths[1].begin(), paths[1].end());
append(paths[0], paths[1]);
paths.pop_back();
} else if (are_connected({paths[0].back()}, {paths[1][0]})) {
append(paths[0], paths[1]);
paths.pop_back();
} else if (are_connected({paths[0][0]}, {paths[1].back()})) {
reverse(paths[0].begin(), paths[0].end());
reverse(paths[1].begin(), paths[1].end());
append(paths[0], paths[1]);
paths.pop_back();
} else if (are_connected({paths[0][0]}, {paths[1][0]})) {
reverse(paths[0].begin(), paths[1].end());
append(paths[0], paths[1]);
paths.pop_back();
} else if (are_connected({i}, {paths[0].back()})) {
paths[0].push_back(i);
i++;
} else if (are_connected({i}, {paths[0][0]})) {
paths[0].insert(paths[0].begin(), i);
i++;
} else if (are_connected({i}, {paths[1].back()})) {
paths[1].push_back(i);
i++;
} else if (are_connected({i}, {paths[1][0]})) {
paths[1].insert(paths[1].begin(), i);
i++;
}
}
}
int nodes_total = 0;
for (vector<int> v : paths) nodes_total += v.size();
assert(paths.size() <= 2);
assert(nodes_total == N);
if (paths.size() == 1 || paths[0].size() > paths[1].size()) return paths[0];
else return paths[1];
}
