#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
vector<int>join(vector<int>&A,vector<int>&B)
{
vector<int>ret=A;
for(int i=0;i<B.size();i++){
ret.push_back(B[i]);
}
return ret;
}
bool are_connected(int a,int b)
{
return are_connected(vector<int>(1,a),vector<int>(1,b));
}
void split(vector<int>&v,int sz,vector<int>&a,vector<int>&b)
{
for(int i=0;i<sz;i++){
a.push_back(v[i]);
}
for(int i=sz;i<v.size();i++){
b.push_back(v[i]);
}
}
void BS(vector<int>A,vector<int>B,int&s,int&e)
{
while(A.size()>1){
vector<int>a,b;
split(A,(A.size())/2,a,b);
if(are_connected(a,B)){
swap(A,a);
}
else{
swap(A,b);
}
}
while(B.size()>1){
vector<int>a,b;
split(B,(B.size())/2,a,b);
if(are_connected(A,a)){
swap(B,a);
}
else{
swap(B,b);
}
}
s=A[0];
e=B[0];
}
std::vector<int> longest_trip(int N, int D)
{
vector<vector<int> >path(N);
for(int i=0;i<N;i++){
path[i].push_back(i);
}
while(path.size()>2){
int sz=path.size();
vector<int>A=path[sz-1],B=path[sz-2],C=path[sz-3];
if(are_connected(A.back(),B[0])){
path.pop_back();
path.pop_back();
path.push_back(join(A,B));
continue;
}
if(are_connected(A.back(),C[0])){
path.pop_back();
path.pop_back();
path.pop_back();
path.push_back(join(A,C));
path.push_back(B);
continue;
}
path.pop_back();
path.pop_back();
path.pop_back();
path.push_back(A);
reverse(all(B));
path.push_back(join(B,C));
}
if(are_connected(path[0][0],path[1][0])){
reverse(all(path[0]));
return join(path[0],path[1]);
}
if(are_connected(path[0][0],path[1].back())){
return join(path[1],path[0]);
}
if(are_connected(path[0].back(),path[1][0])){
return join(path[0],path[1]);
}
if(are_connected(path[0].back(),path[1].back())){
reverse(all(path[1]));
return join(path[0],path[1]);
}
if(!are_connected(path[0],path[1])){
if(path[0].size()>=path[1].size()){
return path[0];
}
return path[1];
}
int c,d;
BS(path[0],path[1],c,d);
for(int i=0;i<path[0].size();i++){
if(path[0][i]==c){
c=i;
break;
}
}
for(int i=0;i<path[1].size();i++){
if(path[1][i]==d){
d=i;
break;
}
}
vector<int>ans;
for(int i=c+1;i<path[0].size();i++){
ans.push_back(path[0][i]);
}
for(int i=0;i<=c;i++){
ans.push_back(path[0][i]);
}
for(int i=d;i<path[1].size();i++){
ans.push_back(path[1][i]);
}
for(int i=0;i<d;i++){
ans.push_back(path[1][i]);
}
return ans;
}
