#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int N, int D) {
vector<int> rem(N);
iota(rem.rbegin(), rem.rend(), 0);
vector<int> path1;
vector<int> path2;
while (!rem.empty()) {
int u = rem.back();
rem.pop_back();
if (path1.empty()) {
path1.push_back(u);
continue;
}
if (path2.empty()) {
path2.push_back(u);
continue;
}
if (rem.empty()) {
if (are_connected({path1.back()}, {u})) {
path1.push_back(u);
continue;
}
if (are_connected({path2.back()}, {u})) {
path2.push_back(u);
continue;
}
path1.insert(path1.end(), path2.rbegin(), path2.rend());
path2 = {u};
continue;
}
int v = rem.back();
rem.pop_back();
if (are_connected({u}, {v})) {
if (are_connected({path1.back()}, {u})) {
path1.push_back(u);
path1.push_back(v);
continue;
}
if (are_connected({path2.back()}, {u})) {
path2.push_back(u);
path2.push_back(v);
continue;
}
path1.insert(path1.end(), path2.rbegin(), path2.rend());
path2 = {u, v};
}
else {
int nxt1 = (are_connected({path1.back()}, {u}) ? u : v);
int nxt2 = (are_connected({path2.back()}, {u}) ? u : v);
if (nxt1 == nxt2) {
path1.push_back(nxt1);
path1.insert(path1.end(), path2.rbegin(), path2.rend());
path2 = {u ^ v ^ nxt1};
}
else {
path1.push_back(nxt1);
path2.push_back(nxt2);
}
}
}
if (path1.empty()) {
return path2;
}
if (path2.empty()) {
return path1;
}
/* vector<pair<int, int>> ends = {{path1[0], path2[0]}, {path1.back(), path2[0]}, {path1[0], path2.back()}};
for (auto [u, v]: ends) {
if (are_connected({u}, {v})) {
if (path1.back() != u) {
reverse(path1.begin(), path1.end());
}
if (path2[0] != v) {
reverse(path2.begin(), path2.end());
}
path1.insert(path1.end(), path2.begin(), path2.end());
return path1;
}
}
if (!are_connected(path1, path2)) {*/
if (path1.size() > path2.size()) {
return path1;
}
else {
return path2;
}
//}
vector<int> cand1 = path1;
vector<int> cand2 = path2;
for (int iter = 0; iter < 2; iter++) {
while ((int)cand1.size() > 1) {
vector<int> left_cand(cand1.begin(), cand1.begin() + (int)cand1.size() / 2);
vector<int> right_cand(cand1.begin() + (int)cand1.size() / 2, cand1.end());
if (are_connected(left_cand, cand2)) {
cand1.swap(left_cand);
}
else {
cand1.swap(right_cand);
}
}
cand1.swap(cand2);
}
rotate(path1.begin(), path1.end(), find(path1.begin(), path1.end(), cand1[0]));
rotate(path2.begin(), path2.end(), find(path2.begin(), path2.end(), cand2[0]));
path1.insert(path1.begin(), path2.rbegin(), path2.rend());
return path1;
}
