#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
std::vector<int> longest_trip(int N, int D)
{
if(D==3){
vector<int>ret;
for(int i=0;i<N;i++){
ret.push_back(i);
}
return ret;
}else if(D==2){
deque<int>dq;
int now=0;
if(are_connected({0},{1})){
dq.push_back(0);
dq.push_back(1);
now=2;
}else{
dq.push_back(0);
dq.push_back(2);
dq.push_back(1);
now=3;
}
for(;now<N;now++){
if(are_connected({dq.front()},{now})){
dq.push_front(now);
}else{
dq.push_back(now);
}
}
vector<int>ret;
for(auto x:dq){
ret.push_back(x);
}
return ret;
}
int n=N;
vector<int>all;
for(int i=0;i<n;i++){
all.push_back(i);
}
random_shuffle ( all.begin(), all.end() );
vector<vector<int>>ans(2);
ans[0].push_back(all[0]);
for(int i=1;i<n;i++){
int cn0=are_connected({ans[0].back()},{all[i]});
int cn1=0;
if((int)ans[1].size()>0){
if(are_connected({ans[1].back()},{all[i]})){
cn1=1;
}
}
if(cn1==1&&cn0==1){
ans[0].push_back(all[i]);
while((int)ans[1].size()>0){
ans[0].push_back(ans[1].back());
ans[1].pop_back();
}
}else if(cn0==1){
ans[0].push_back(all[i]);
}else{
ans[1].push_back(all[i]);
}
}
if((int)ans[0].size()<(int)ans[1].size()){
swap(ans[0],ans[1]);
}
vector<int>ret;
if((int)ans[1].size()==0){
return ans[0];
}
if(ans[0][0]!=ans[0].back()&&!are_connected({ans[0][0]},{ans[0].back()})){
if(are_connected({ans[0].back()},{ans[1].back()})){
for(int i=(int)ans[1].size()-1;i>=0;i--){
ans[0].push_back(ans[1][i]);
}
}else{
for(int i=0;i<(int)ans[0].size();i++){
ans[1].push_back(ans[0][i]);
}
swap(ans[0],ans[1]);
}
return ans[0];
}else if(ans[1][0]!=ans[1].back()&&!are_connected({ans[1][0]},{ans[1].back()})){
swap(ans[0],ans[1]);
if(are_connected({ans[0].back()},{ans[1].back()})){
for(int i=(int)ans[1].size()-1;i>=0;i--){
ans[0].push_back(ans[1][i]);
}
}else{
for(int i=0;i<(int)ans[0].size();i++){
ans[1].push_back(ans[0][i]);
}
swap(ans[0],ans[1]);
}
return ans[0];
}else{
if(!are_connected(ans[0],ans[1])){
return ans[0];
}
int low1=0,high1=(int)ans[0].size(),mid1;
while(high1-low1>1){
mid1=(high1+low1)>>1;
vector<int>bal;
for(int i=mid1;i<high1;i++){
bal.push_back(ans[0][i]);
}
if(are_connected(bal,ans[1])){
low1=mid1;
}else{
high1=mid1;
}
}
int low2=0,high2=(int)ans[1].size(),mid2;
while(high2-low2>1){
mid2=(high2+low2)>>1;
vector<int>paee;
for(int i=mid2;i<high2;i++){
paee.push_back(ans[1][i]);
}
if(are_connected({ans[0][low1]},paee)){
low2=mid2;
}else{
high2=mid2;
}
}
for(int i=low1-1;i>=0;i--){
ret.push_back(ans[0][i]);
}
for(int i=(int)ans[0].size()-1;i>=low1;i--){
ret.push_back(ans[0][i]);
}
for(int i=low2;i<(int)ans[1].size();i++){
ret.push_back(ans[1][i]);
}
for(int i=0;i<low2;i++){
ret.push_back(ans[1][i]);
}
}
return ret;
}
