#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>bool maximize(T& a, T b){
if(a < b){
a = b;
return true;
}
return false;
}
int n, d;
namespace sub1{
vector<int>solve(){
vector<int>p(n);
iota(p.begin(), p.end(), 0);
return p;
}
}
namespace sub2{
vector<int>solve(){
deque<int>d = {0};
int other;
if(are_connected({0}, {1})){
d.push_back(other = 1);
}
else{
d.push_back(other = 2);
}
for(int i = 1; i < n; i++){
if(i != other){
if(are_connected({i}, {d.back()})){
d.push_back(i);
}
else{
d.push_front(i);
}
}
}
return vector<int>(d.begin(), d.end());
}
}
namespace sub34{
vector<int>solve(){
vector<int>p1 = {0}, p2 = {1};
for(int i = 2; i < n; i += 2){
if(i + 1 == n){
if(are_connected({p1.back()}, {i})){
p1.push_back(i);
}
else if(p2.empty() || are_connected({p2.back()}, {i})){
p2.push_back(i);
}
else{
p1.insert(p1.end(), p2.rbegin(), p2.rend());
p2 = {i};
}
}
else if(are_connected({i}, {i + 1})){
if(are_connected({i}, {p1.back()})){
p1.push_back(i);
p1.push_back(i + 1);
}
else if(are_connected({i}, {p2.back()})){
p2.push_back(i);
p2.push_back(i + 1);
}
else{
p1.insert(p1.end(), p2.rbegin(), p2.rend());
p2 = {i, i + 1};
}
}
else{
if(are_connected({i}, {p1.back()})){
p1.push_back(i);
}
else{
p1.push_back(i + 1);
}
if(are_connected({i}, {p2.back()})){
if(p1.back() == i){
p1.insert(p1.end(), p2.rbegin(), p2.rend());
p2 = {i + 1};
}
else{
p2.push_back(i);
}
}
else if(p1.back() == i + 1){
p1.insert(p1.end(), p2.rbegin(), p2.rend());
p2 = {i};
}
else{
p2.push_back(i + 1);
}
}
}
if(p1.size() < p2.size()){
swap(p1, p2);
}
if(are_connected({p1[0]}, {p2[0]})){
p1.insert(p1.begin(), p2.rbegin(), p2.rend());
return p1;
}
if(are_connected({p1.back()}, {p2[0]})){
p1.insert(p1.end(), p2.begin(), p2.end());
return p1;
}
if(are_connected({p1[0]}, {p2.back()})){
p2.insert(p2.end(), p1.begin(), p1.end());
return p2;
}
if(!are_connected(p1, p2)){
return p1;
}
int pi1 = int(p1.size()) - 1, pi2 = int(p2.size()) - 1, low = 0, high = pi1 - 1;
while(low <= high){
int mid = (low + high) >> 1;
if(are_connected(vector<int>(p1.begin(), p1.begin() + mid + 1), p2)){
high = (pi1 = mid) - 1;
}
else{
low = mid + 1;
}
}
low = 0;
high = pi2 - 1;
while(low <= high){
int mid = (low + high) >> 1;
if(are_connected({p1[pi1]}, vector<int>(p2.begin(), p2.begin() + mid + 1))){
high = (pi2 = mid) - 1;
}
else{
low = mid + 1;
}
}
vector<int>ans(p1.begin(), p1.begin() + pi1 + 1);
ans.insert(ans.end(), p2.begin() + pi2, p2.end());
ans.insert(ans.end(), p2.begin(), p2.begin() + pi2);
for(int i = int(p1.size()) - 1; i > pi1; i--){
ans.insert(ans.begin(), p1[i]);
}
return ans;
}
}
vector<int>longest_trip(int N, int D){
n = N;
if((d = D) == 3){
return sub1::solve();
}
if(d == 2){
return sub2::solve();
}
return sub34::solve();
}
