#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) 42
#endif
using ll = long long;
#define all(v) v.begin(), v.end()
#define len(v) int(v.size())
const ll INF = 1e18;
bool are_connected(vector<int> A, vector<int> B);
vector<int> longest_trip(int N, int D) {
if (D == 3) {
vector<int> res(N);
iota(all(res), 0);
return res;
}
set<vector<int>> p;
for (int i = 0; i < N; i++) p.insert({i});
while (len(p) > 2) {
auto v = *p.begin(), u = *next(p.begin()), w = *next(next(p.begin()));
vector<int> x;
if (are_connected({v[0]}, {u[0]})) {
x = v;
reverse(all(x));
for (int el : u) x.push_back(el);
p.erase(v);
p.erase(u);
}
else if (are_connected({v[0]}, {w[0]})) {
x = v;
reverse(all(x));
for (int el : w) x.push_back(el);
p.erase(v);
p.erase(w);
}
else {
x = u;
reverse(all(x));
for (int el : w) x.push_back(el);
p.erase(u);
p.erase(w);
}
p.insert(x);
}
vector a = *p.begin(), b = *prev(p.end());
if (len(a) < len(b)) swap(a, b);
int best_i = -1, best_j = -1, best = len(a);
for (int i = 0; i < len(a); i++) {
for (int j = 0; j < len(b); j++) {
int v = a[i], u = b[j];
if (are_connected({v}, {u})) {
int l = max(i + 1, len(a) - i) + max(j + 1, len(b) - j);
if (l > best) {
best_i = i;
best_j = j;
best = l;
}
}
}
}
if (best_i == -1) {
return a;
}
else {
vector<int> x;
if (best_i + 1 > len(a) - best_i) {
for (int i = 0; i <= best_i; i++) {
x.push_back(a[i]);
}
}
else {
for (int i = len(a) - 1; i >= best_i; i--) {
x.push_back(a[i]);
}
}
if (best_j + 1 > len(b) - best_j) {
for (int j = best_j; j >= 0; j--) {
x.push_back(b[j]);
}
}
else {
for (int j = best_j; j < len(b); j++) {
x.push_back(b[j]);
}
}
return x;
}
}
