#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int N, int D){
vector<int> v1 = {0}, v2 = {1};
bool gnc = 0;
for (int i = 2; i < N; i++){
if (gnc){
if (are_connected({v1.back()}, {i})){
v1.push_back(i); gnc = 0;
}
else{
v2.push_back(i); gnc = 1;
}
}
else{
if (are_connected({v1.back()}, {i})){
v1.push_back(i); gnc = 0;
}
else if (are_connected({v2.back()}, {i})){
v2.push_back(i); gnc = 1;
}
else{
if (i + 1 < N){
bool conn = are_connected({i}, {i + 1});
if (!conn) v1.push_back(i + 1);
for (int j = v2.size() - 1; j >= 0; j--) v1.push_back(v2[j]);
v2 = {i};
if (conn) v2.push_back(i + 1);
i++;
}
else{
for (int j = v2.size() - 1; j >= 0; j--) v1.push_back(v2[j]);
v2 = {i};
}
gnc = 0;
}
}
}
if (!are_connected(v1, v2)) return (v1.size() >= v2.size() ? v1 : v2);
vector<int> qv1 = {v1[0]}, qv2 = {v2[0]};
if (v1.size() != 1) qv1.push_back(v1.back());
if (v2.size() != 1) qv2.push_back(v2.back());
if (are_connected(qv1, qv2)){
int v1e;
if (are_connected({v1.back()}, qv2)) v1e = v1.back();
else{
v1e = v1[0]; reverse(v1.begin(), v1.end());
}
if (are_connected({v1e}, {v2.back()})) reverse(v2.begin(), v2.end());
for (int x : v2) v1.push_back(x);
return v1;
}
int lo = 0, hi = v1.size() - 1;
while (lo < hi){
int m = (lo + hi) >> 1;
vector<int> qv;
for (int i = lo; i <= m; i++) qv.push_back(v1[i]);
if (are_connected(qv, v2)) hi = m;
else lo = m + 1;
}
int c1 = hi;
lo = 0, hi = v2.size() - 1;
while (lo < hi){
int m = (lo + hi) >> 1;
vector<int> qv;
for (int i = lo; i <= m; i++) qv.push_back(v2[i]);
if (are_connected({v1[c1]}, qv)) hi = m;
else lo = m + 1;
}
int c2 = hi;
vector<int> ans;
for (int i = c1 - 1; i >= 0; i--) ans.push_back(v1[i]);
for (int i = v1.size() - 1; i >= c1; i--) ans.push_back(v1[i]);
for (int i = c2; i >= 0; i--) ans.push_back(v2[i]);
for (int i = v2.size() - 1; i > c2; i--) ans.push_back(v2[i]);
return ans;
}
