#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
vi longest_trip(int N, int D) {
int n = N, d = D;
vi ans;
if (d == 3) {
ans.resize(n); iota(ans.begin(), ans.end(), 0);
return ans;
} else if (d == 1) {
int a = 0, b = 1;
vi p1(1, a), p2(1, b);
for (int i = 2; i < n; i++) {
if (are_connected({a}, {i})) {
p1.push_back(i);
a = i;
} else if (are_connected({b}, {i})) {
p2.push_back(i);
b = i;
} else {
while (!p2.empty()) {
p1.push_back(p2.back());
p2.pop_back();
}
a = p1.back();
p2.push_back(i);
b=i;
}
}
if (!are_connected(p1, p2)) {
return p1.size() > p2.size() ? p1 : p2;
} else {
if (are_connected({p1[0]}, {p2[0]})) {
reverse(p1.begin(), p1.end());
for (auto &el : p2) p1.push_back(el);
return p1;
} else if (are_connected({p1[0]}, {p2.back()})) {
swap(p1, p2);
for (auto &el : p2) p1.push_back(el);
return p1;
} else if (are_connected({p1.back()}, {p2[0]})) {
for (auto &el : p2) p1.push_back(el);
return p1;
} else if (are_connected({p1.back()}, {p2.back()})) {
reverse(p2.begin(), p2.end());
for (auto &el : p2) p1.push_back(el);
return p1;
} else {
for (int i = 1; i < p2.size(); i++) {
if (are_connected({p2[i]}, {p1.back()})) {
for (int j = i; j < p2.size(); j++) p1.push_back(p2[j]);
for (int j = 0; j < i; j++) p1.push_back(p2[j]);
return p1;
}
}
}
}
}
return ans;
}
