#include "longesttrip.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
bool check (int x, int y) {
assert(x != y);
return are_connected({x}, {y});
}
vector <int> longest_trip (int n, int d) {
vector <int> x, y;
x.push_back(0);
y.push_back(1);
for (int i = 2; i + 1 < n; i += 2) {
int u = i, v = i + 1;
if (check(u, v)) {
if (check(u, x.back())) {
x.push_back(u); x.push_back(v);
} else if (check(u, y.back())) {
y.push_back(u); y.push_back(v);
} else {
reverse(y.begin(), y.end());
for (auto j : y) {
x.push_back(j);
}
y.clear();
y.push_back(u); y.push_back(v);
}
} else { //preferably make a flowchart for this part
if (check(u, x.back())) {
x.push_back(u);
if (check(v, y.back())) {
y.push_back(v);
} else {
reverse(y.begin(), y.end());
for (auto j : y) {
x.push_back(j);
}
y.clear();
y.push_back(v);
}
} else {
x.push_back(v);
if (check(u, y.back())) {
y.push_back(u);
} else {
reverse(y.begin(), y.end());
for (auto j : y) {
x.push_back(j);
}
y.clear();
y.push_back(u);
}
}
}
}
if (n & 1) {
int i = n - 1;
bool f = check(x.back(), i);
bool g = check(y.back(), i);
if (!f && !g) {
reverse(y.begin(), y.end());
for (auto j : y) {
x.push_back(j);
}
y.clear();
y.push_back(i);
} else if (f) {
x.push_back(i);
} else {
y.push_back(i);
}
}
if (!are_connected(x, y)) {
if (x.size() < y.size()) {
swap(x, y);
}
return x;
}
vector <int> gg = {x.front()}, hh = {y.front()};
if (x.size() != 1) gg.push_back(x.back());
if (y.size() != 1) hh.push_back(y.back());
for (auto i : gg) {
for (auto j : hh) {
if (are_connected({i}, {j})) {
if (i == x.front()) {
reverse(x.begin(), x.end());
}
if (j == y.back()) {
reverse(y.begin(), y.end());
}
for (auto g : y) {
x.push_back(g);
}
return x;
}
}
}
int L1 = 0, R1 = int(x.size()) - 1, ANS1 = -1;
while (L1 <= R1) {
int mid = (L1 + R1) / 2;
vector <int> dd;
for (int i = 0; i <= mid; i++) {
dd.push_back(x[i]);
}
if (are_connected(dd, y)) {
R1 = mid - 1; ANS1 = mid;
} else {
L1 = mid + 1;
}
}
for (int i = ANS1; i <= ANS1; i++) {
int l = 0, r = int(y.size()) - 1, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
vector <int> dd;
for (int j = 0; j <= mid; j++) {
dd.push_back(y[j]);
}
if (are_connected({x[i]}, dd)) {
r = mid - 1; ans = mid;
} else {
l = mid + 1;
}
}
if (ans == -1) continue;
vector <int> ret;
for (int j = i - 1; j >= 0; j--) {
ret.push_back(x[j]);
}
for (int j = int(x.size()) - 1; j > i; j--) {
ret.push_back(x[j]);
}
ret.push_back(x[i]);
ret.push_back(y[ans]);
for (int j = ans + 1; j < int(y.size()); j++) {
ret.push_back(y[j]);
}
for (int j = 0; j < ans; j++) {
ret.push_back(y[j]);
}
return ret;
}
}
