#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> longest_trip(int N, int D) {
mt19937 rnd(228);
vector<int> a, b, ord(N);
iota(ord.begin(), ord.end(), 0);
shuffle(ord.begin(), ord.end(), rnd);
int known = -1;
for (int x : ord) {
if (a.empty() || b.empty()) {
(a.empty() ? a : b).push_back(x);
continue;
}
if (rnd() % 2) {
swap(a, b);
}
if (0) {
int res = are_connected({a.back()}, {x});
if (res == 1) {
a.push_back(x);
known = -1;
} else if (known != -1) {
if (known == 1) { // unreachable
a.insert(a.end(), b.rbegin(), b.rend());
b = {x};
known = -1;
} else {
b.push_back(x);
known = 0;
}
} else {
res = are_connected({b.back()}, {x});
if (res == 0) {
a.insert(a.end(), b.rbegin(), b.rend());
b = {x};
known = -1;
} else {
b.push_back(x);
known = 0;
}
}
} else {
if (are_connected({a.back()}, {x})) {
a.push_back(x);
} else if (are_connected({b.back()}, {x})) {
b.push_back(x);
} else {
a.insert(a.end(), b.rbegin(), b.rend());
b = {x};
}
}
}
if (a.empty() || b.empty() || !are_connected(a, b)) {
return a.size() > b.size() ? a : b;
}
if (size(a) < size(b)) {
swap(a, b);
}
if (!are_connected(a, {b[0]})) {
int lo = 0, hi = size(b);
while (lo + 1 < hi) {
int mid = lo + hi >> 1;
if (are_connected(a, vector(b.begin(), b.begin() + mid))) {
hi = mid;
} else {
lo = mid;
}
}
rotate(b.begin(), b.begin() + lo, b.end());
}
assert(are_connected(a, {b[0]}));
if (are_connected({a[0], a.back()}, {b[0]})) {
if (are_connected({a[0]}, {b[0]})) {
reverse(a.begin(), a.end());
}
a.insert(a.end(), b.begin(), b.end());
return a;
} else {
int lo = 0, hi = size(b);
while (lo + 1 < hi) {
int mid = lo + hi >> 1;
if (are_connected(vector(a.begin(), a.begin() + mid), {b[0]})) {
hi = mid;
} else {
lo = mid;
}
}
rotate(a.begin(), a.begin() + hi, a.end());
a.insert(a.end(), b.begin(), b.end());
return a;
}
}
