#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
vector<int> longest_trip(int N, int D){
vector<int> prv(N, -1), nxt(N, -1);
long long int notret = -1, notb = -1, b = 0, nw = 0;
bool flag = false;
for (int i = 1; i < N; i++){
int k = are_connected({ nw }, { i });
if (k == false){
if (notret == -1){
notret = i;
notb = i;
}else{
if (flag){
k = false;
}else{
k = are_connected({ nw }, { notret });
}
if (k == false){
prv[notret] = i;
nxt[i] = notret;
notret = i;
flag = true;
}else{
nxt[nw] = notret;
prv[notret] = nw;
nw = notb;
notb = i;
notret = i;
}
}
}else{
nxt[nw] = i;
prv[i] = nw;
nw = i;
flag = false;
}
}
vector<int> ret;
if (notret == -1){
for (int i = b; i != -1; i = nxt[i]) ret.push_back(i);
}else{
swap(notb, notret);
vector<int> yl1, yl2;
for (int i = b; i != -1; i = nxt[i]) yl1.push_back(i);
for (int i = notb; i != -1; i = nxt[i]) yl2.push_back(i);
int k = are_connected(yl1, yl2);
if (k == false){
if (yl1.size() > yl2.size()){
ret = yl1;
}else{
ret = yl2;
}
}else{
if (yl2.size() == 1){
k = are_connected({ yl2.back() }, { yl1.back(), yl1.front() });
}else if (yl1.size() == 1){
k = are_connected({ yl2.back(), yl2.front() }, { yl1.back() });
}else{
k = are_connected({ yl2.back(), yl2.front() }, { yl1.back(), yl1.front() });
}
if (k == true){
if (yl1.size() == 1){
for (int i = 0; i < yl1.size(); i++) ret.push_back(yl1[i]);
if (yl2.size() == 1){
for (int i = 0; i < yl2.size(); i++) ret.push_back(yl2[i]);
}else{
if (yl1.size() == 1){
k = are_connected( { yl1.back() }, { yl2.front() } );
}else{
k = are_connected( { yl1.back(), yl1.front() }, { yl2.front() } );
}
if (k){
for (int i = 0; i < yl2.size(); i++) ret.push_back(yl2[i]);
}else{
for (int i = yl2.size() - 1; i >= 0; i--) ret.push_back(yl2[i]);
}
}
return ret;
}
if (yl2.size() == 1){
if (yl2.size() == 1){
k = are_connected( { yl1.back() }, { yl2.back() } );
}else{
k = are_connected( { yl1.back() }, { yl2.back(), yl2.front() } );
}
if (k){
for (int i = 0; i < yl1.size(); i++) ret.push_back(yl1[i]);
}else{
for (int i = yl1.size() - 1; i >= 0; i--) ret.push_back(yl1[i]);
}
for (int i = 0; i < yl2.size(); i++) ret.push_back(yl2[i]);
return ret;
}
k = are_connected( { yl1.back() }, { yl2.front() } );
if (k){
for (int i = 0; i < yl1.size(); i++) ret.push_back(yl1[i]);
for (int i = 0; i < yl2.size(); i++) ret.push_back(yl2[i]);
return ret;
}
k = are_connected( { yl1.back() }, { yl2.back() } );
if (k){
for (int i = 0; i < yl1.size(); i++) ret.push_back(yl1[i]);
for (int i = yl2.size() - 1; i >= 0; i--) ret.push_back(yl2[i]);
return ret;
}
k = are_connected( { yl1.front() }, { yl2.front() } );
if (k){
for (int i = yl1.size() - 1; i >= 0; i--) ret.push_back(yl1[i]);
for (int i = 0; i < yl2.size(); i++) ret.push_back(yl2[i]);
return ret;
}
for (int i = yl1.size() - 1; i >= 0; i--) ret.push_back(yl1[i]);
for (int i = yl2.size() - 1; i >= 0; i--) ret.push_back(yl2[i]);
return ret;
}
vector<int> src;
int add = 0, add2 = 0;
reverse(all(yl1));
for (int i = ceil(log2(yl1.size())) - 1; i >= 0; i--){
i = min(i, (int)ceil(log2(yl1.size() - add)) - 1);
if (i == -1)
break;
src.clear();
for (int o = 0; o < (1LL << i); o++){
src.push_back(yl1[o + add]);
}
k = are_connected(src, yl2);
if (k == false){
add += (1LL << i);
}
}
add = yl1.size() - 1 - add;
reverse(all(yl1));
for (int i = ceil(log2(yl2.size())) - 1; i >= 0; i--){
i = min(i, (int)ceil(log2(yl2.size() - add2)) - 1);
if (i == -1)
break;
src.clear();
for (int o = 0; o < (1LL << i); o++){
src.push_back(yl2[o + add2]);
}
k = are_connected(src, { yl1[add] });
if (k == false){
add2 += (1LL << i);
}
}
if (add != yl1.size() - 1){
prv[b] = nw;
nxt[nw] = b;
b = nxt[yl1[add]];
prv[nxt[yl1[add]]] = -1;
}
if (add2){
prv[notb] = notret;
nxt[notret] = notb;
nxt[prv[yl2[add2]]] = -1;
}
nxt[yl1[add]] = yl2[add2];
prv[yl2[add2]] = yl1[add];
ret.clear();
for (int i = b; i != -1; i = nxt[i]) ret.push_back(i);
}
}
return ret;
}
