#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << "----> " << x << endl;
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")
int n;
ll bins(vector<int> &v, vector<int> &v1){
ll l = -1,r = v1.size() - 1;
while(r > l + 1){
ll mid = l + (r - l) / 2;
vector<int> vv;
for(int i = 0; i <= mid; i++) vv.pb(v1[i]);
if(are_connected(vv, v)) r = mid;
else l = mid;
}
return r;
}
std::vector<int> longest_trip(int N, int D){
n = N;
vector<int> v[2];
v[0].pb(0);
v[1].pb(1);
bool ok = false;
for(int i = 2; i < n; i++){
bool x = are_connected({v[0][v[0].size() - 1]}, {i});
if(x){
ok = false;
v[0].pb(i);
continue;
}
if(ok) v[1].pb(i);
else{
ok = true;
bool y = are_connected({v[1][v[1].size() - 1]}, {i});
if(y) v[1].pb(i);
else{
if(v[0].size() < v[1].size()) swap(v[0], v[1]);
reverse(v[1].begin(), v[1].end());
for(auto it : v[1]) v[0].pb(it);
ok = (v[1].size() == 1);
v[1].clear();
v[1].pb(i);
}
}
}
// for(int i = 1; i < v[0].size(); i++) assert(are_connected({v[0][i]}, {v[0][i - 1]}));
// for(int i = 1; i < v[1].size(); i++) assert(are_connected({v[1][i]}, {v[1][i - 1]}));
if(!are_connected(v[0], v[1])){
if(v[0].size() >= v[1].size()) return v[0];
return v[1];
}
bool x = are_connected({v[1][v[1].size() - 1]}, {v[0][v[0].size() - 1]}),
y = are_connected({v[1][0]}, {v[0][v[0].size() - 1]}),z = are_connected({v[1][v[1].size() - 1]}, {v[0][0]});
if(z){
swap(v[0], v[1]);
y = true;
}
else if(x){
reverse(v[1].begin(), v[1].end());
y = true;
}
if(y){
for(auto it : v[1]) v[0].pb(it);
return v[0];
}
int idx = bins(v[1], v[0]);
vector<int> vv = {v[0][idx]};
int idx1 = bins(vv, v[1]);
vector<int> ans;
for(int i = idx + 1; i < v[0].size(); i++) ans.pb(v[0][i]);
for(int i = 0; i <= idx; i++) ans.pb(v[0][i]);
for(int i = idx1; i < v[1].size(); i++) ans.pb(v[1][i]);
for(int i = 0; i < idx1; i++) ans.pb(v[1][i]);
return ans;
}
