#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>; using vi = vector<ll>;
vector<ll> longest_trip(ll N, ll D) {
vector<ll> va = {0}; bool conA = 0;
vector<ll> vb = {1}; bool conB = 0;
queue<ll> rnum;
vector<ll> vy,vn; //connected: yes, no
ll x0; //current center
for (ll i=2;i<N;i++) {
rnum.push(i);
}
while (!rnum.empty()) {
vy.clear(); vn.clear();
x0 = rnum.front(); rnum.pop();
conA = are_connected((vi){va[0]},(vi){x0});
conB = are_connected((vi){vb[0]},(vi){x0});
if (conA&&conB) {
vector<ll> van;
for (ll i=(va.size()-1);i>=0;i--) {
van.push_back(va[i]);
}
van.push_back(x0);
for (ll i=0;i<(vb.size());i++) {
van.push_back(vb[i]);
}
va = van;
vb.clear();
if (rnum.empty()) {
break;
}
vb.push_back(rnum.front()); rnum.pop();
continue;
}
while ((((ll)conA)+((ll)conB)+vy.size())<2 && !rnum.empty()) {
ll x1 = rnum.front(); rnum.pop();
if (are_connected((vi){x1},(vi){x0})) {
vy.push_back(x1);
} else {
vn.push_back(x1);
}
}
if (conA) {
vector<ll> van = vy;
van.push_back(x0);
vector<ll> vbn = vn;
for (ll x2: va) {
van.push_back(x2);
}
for (ll x2: vb) {
vbn.push_back(x2);
}
va = van; vb = vbn;
} else if (conB) {
vector<ll> van = vy;
van.push_back(x0);
vector<ll> vbn = vn;
for (ll x2: vb) {
van.push_back(x2);
}
for (ll x2: va) {
vbn.push_back(x2);
}
va = van; vb = vbn;
} else {
assert(!conB && !conA);
vector<ll> van;
for (ll i=(vb.size()-1);i>=0;i--) {
van.push_back(vb[i]);
}
for (ll x2: vn) {
van.push_back(x2);
}
for (ll i=0;i<va.size();i++) {
van.push_back(va[i]);
}
va = van;
if (vy.size()==2) {
vb = (vi){vy[0],x0,vy[1]};
} else if (vy.size()==1) {
vb = (vi){vy[0],x0};
} else {
assert(vy.size()==0);
vb = (vi){x0};
}
}
}
assert(va.size()+vb.size()==N);
if (va.size()==0) {
return vb;
}
if (vb.size()==0) {
return va;
}
if (va.size()<vb.size()) {
swap(va,vb);
}
//thus va size >= vb size -> va size >= 2
if (are_connected((vi){va[0]},(vi){vb[0]})) {
vector<ll> vf;
for (ll i=(va.size()-1);i>=0;i--) {
vf.push_back(va[i]);
}
for (ll i=0;i<vb.size();i++) {
vf.push_back(vb[i]);
}
return vf;
}
if (are_connected((vi){va[0]},(vi){vb[vb.size()-1]})) {
vector<ll> vf;
for (ll i=(va.size()-1);i>=0;i--) {
vf.push_back(va[i]);
}
for (ll i=(vb.size()-1);i>=0;i++) {
vf.push_back(vb[i]);
}
return vf;
}
//flip va
if (are_connected((vi){va[va.size()-1]},(vi){vb[0]})) {
vector<ll> vf;
for (ll i=0;i<va.size();i++) {
vf.push_back(va[i]);
}
for (ll i=0;i<vb.size();i++) {
vf.push_back(vb[i]);
}
return vf;
}
if (are_connected((vi){va[va.size()-1]},(vi){vb[vb.size()-1]})) {
vector<ll> vf;
for (ll i=0;i<va.size();i++) {
vf.push_back(va[i]);
}
for (ll i=(vb.size()-1);i>=0;i++) {
vf.push_back(vb[i]);
}
return vf;
}
//now both sequences are cyclized
if (!are_connected(va,vb)) {
if (va.size()<vb.size()) {
return vb;
} else {
return va;
}
}
ll xmin = 0; ll xmax = va.size()-1;
while (xmin<xmax) {
ll xt = (xmin+xmax)/2;
vector<ll> vqry;
for (ll x0=xmin;x0<=xt;x0++) {
vqry.push_back(va[x0]);
}
if (are_connected(vqry,vb)) {
xmax = xt;
} else {
xmin = xt+1;
}
}
vi va1 = {va[xmin]};
ll ymin = 0; ll ymax = vb.size()-1;
while (ymin<ymax) {
ll yt = (ymin+ymax)/2;
vector<ll> vqry;
for (ll y0=ymin;y0<=yt;y0++) {
vqry.push_back(vb[y0]);
}
if (are_connected(va1,vqry)) {
ymax = yt;
} else {
ymin = yt+1;
}
}
vector<ll> vfin;
for (ll i=0;i<(vb.size());i++) {
vfin.push_back(vb[(i+1+ymin)%vb.size()]);
}
for (ll i=0;i<va.size();i++) {
vfin.push_back(va[(i+xmin)%va.size()]);
}
return vfin;
// if (are_connected((vi)va[va.size()-1],vb)) {
// //binary search for vb first location
// vi AP = {va[va.size()-1]};
// ll xmin = 0; ll xmax = vb.size()-1;
// while (xmin<xmax) {
// ll xt = (xmin+xmax)/2;
// vector<ll> vqry;
// for (ll x0=xmin;x0<=xt;x0++) {
// vqry.push_back(vb[xt]);
// }
// if (are_connected(AP,vqry)) {
// xmax = xt;
// } else {
// xmin = xt+1;
// }
// }
// vector<ll> vf = va;
// for (ll x0=0;x0<vb.size();x0++) {
// vf.push_back(vb[(x0+xmin)%(vb.size())]);
// }
// return vf;
// }
}
