#include "longesttrip.h"
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define ln "\n"
ll n, d;
pair<ll, vector<ll>> mx;
vector<int> longest_trip(int N, int D)
{
n=N; d=D;
vector<int> a = {0}, b = {1};
bool lost=0;
for (int i=2; i<N; i++){
if (are_connected({a.back()}, {i})){
a.push_back(i);
}else if (lost or are_connected({b.back()}, {i})){
b.push_back(i);
}else{
if (lost) assert(false);
lost=1;
assert(are_connected({a.back()}, {b.back()}));
while (!b.empty()){
a.push_back(b.back());
b.pop_back();
}
b.push_back(i);
}
}
// for (auto ch:a) cout << ch << " ";
// cout << ln;
// for (auto ch:b) cout << ch << " ";
// cout << ln;
if (a.empty() or b.empty()){
return a.empty()?b:a;
}else if (are_connected({a[0]}, {b[0]})){
reverse(a.begin(), a.end());
for (auto ch:b) a.push_back(ch);
return a;
}else if (are_connected({a[0]}, {b.back()})){
for (auto ch:a) b.push_back(ch);
return b;
}else if (are_connected({a.back()}, {b[0]})){
for (auto ch:b) a.push_back(ch);
return a;
}else if (are_connected({a.back()}, {b.back()})){
reverse(b.begin(), b.end());
for (auto ch:b) a.push_back(ch);
return a;
}else if (are_connected(a, b)){
// cout << "Happening" << endl;
ll l=0, r=a.size();
while (l<r){
vector<int> test;
ll mid = (l+r)/2;
for (ll i=l; i<=mid; i++){
test.push_back(a[i]);
}
if (are_connected(test, b)){
r=mid;
}else l=mid+1;
}
int conA = r;
l=0; r=b.size();
while (l<r){
vector<int> test;
ll mid = (l+r)/2;
for (ll i=l; i<=mid; i++){
test.push_back(b[i]);
}
if (are_connected(test, {conA})){
r=mid;
}else l=mid+1;
}
int conB = r;
vector<int> res;
for (int i=conA+1; i<(int)a.size(); i++){
res.push_back(a[i]);
}
for (int i=0; i<=conA; i++){
res.push_back(a[i]);
}
// cout << a[conA] << " " << b[conB] << endl;
for (int i=conB; i<(int)b.size(); i++) res.push_back(b[i]);
for (int i=0; i<conB; i++) res.push_back(b[i]);
return res;
}else{
if (a.size()>b.size()) return a;
else return b;
}
}
