#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> 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(){
deque<int> d, q;
d.append(0);
vector<int> 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);
while(!d.empty()){
ans.append(d.front());
d.pop_front();
}
return ans;
}
vector<int> longest_trip(int N, int D){
n = N;
if(D == 3)
return solve3();
if(D == 2)
return solve2();
return solve1();
}
