#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
int n;
vector<int> get(vector<int> & v, int x){
vector<int> ans;
for(int i = 0; i < x; i++)
ans.append(v[i]);
return ans;
}
vector<int> solve3(){
vector<int> v;
for(int i = 0; i < n; i++)
v.append(i);
return v;
}
vector<int> solve2(){
deque<int> Q;
Q.append(0);
if(are_connected({0}, {1})){
Q.append(1);
if(are_connected({1}, {2}))
Q.append(2);
else Q.push_front(2);
}
else
Q.append(2), Q.append(1);
for(int i = 3; i < n; i++){
if(are_connected({Q.back()}, {i}))
Q.append(i);
else Q.push_front(i);
}
vector<int> ans;
while(!Q.empty()){
ans.append(Q.front());
Q.pop_front();
}
return ans;
}
vector<int> solve1(){
int l, r;
deque<int> d, q, t;
d.append(0);
vector<int> x, y, ans;
for(int i = 1; i < n; i++){
if(are_connected({d.back()}, {i})){
d.append(i);
if(!q.empty() && are_connected({i}, {q.back()})){
while(!q.empty()){
d.append(q.back());
q.pop_back();
}
}
}
else q.append(i);
}
if(d.size() < q.size()) swap(d, q);
t = d;
while(!t.empty()){
x.append(t.front());
t.pop_front();
}
t = q;
while(!t.empty()){
y.append(t.front());
t.pop_front();
}
if(y.empty() || !are_connected(x, y))
return x;
if(!are_connected({x[0]}, {x.back()})){
if(are_connected({x[0]}, {y[0]}))
reverse(all(x));
for(auto & i : x)
ans.append(i);
for(auto & i : y)
ans.append(i);
return ans;
}
if(y.size() > 1 && !are_connected({y[0]}, {y.back()})){
if(are_connected({y[0]}, {x[0]}))
reverse(all(y));
for(auto & i : y)
ans.append(i);
for(auto & i : x)
ans.append(i);
return ans;
}
l = r = 0;
for(int i = 128; i > 0; i /= 2)
if(l + i < x.size() && !are_connected(get(x, l + i), y))
l += i;
for(int i = 128; i > 0; i /= 2)
if(r + i < y.size() && !are_connected({x[l]}, get(y, r + i)))
r += i;
for(int i = l + 1; i < x.size(); i++)
ans.append(x[i]);
for(int i = 0; i <= l; i++)
ans.append(x[i]);
for(int i = r; i < y.size(); i++)
ans.append(y[i]);
for(int i = 0; i < r; i++)
ans.append(y[i]);
return ans;
}
vector<int> longest_trip(int N, int D){
n = N;
if(D == 3)
return solve3();
if(D == 2)
return solve2();
return solve1();
}
