#include "longesttrip.h"
#include "bits/stdc++.h"
using namespace std;
#define len(x) (int)(x.size())
#define all(x) x.begin(), x.end()
#define inf 1000'000'000'000'000'000LL
#define bit(x, i) (((x) >> i) & 1)
template<typename T>
using vec = vector<T>;
std::vector<int> longest_trip(int n, int d) {
mt19937 rnd(14345);
if (d == 3) {
vec<int> ans(n);
iota(all(ans), 0);
return ans;
}
if (d == 2) {
deque<int> ans;
int cur = 0;
ans.push_back(cur);
set<int> not_used;
for (int i = 1; i < n; i++) {
not_used.insert(i);
}
while (true) {
if (not_used.empty()) break;
vec<int> next(all(not_used));
int nxt = next[0];
if (are_connected({cur}, {nxt})) {
ans.push_back(nxt);
not_used.erase(nxt);
cur = nxt;
} else {
if (next.size() == 1) {
ans.push_front(next[0]);
break;
} else {
int net = next[1];
ans.push_back(net);
not_used.erase(net);
cur = net;
}
}
}
return vec<int>(all(ans));
} else {
auto attempt = [&]() {
deque<int> ans;
int cur = rnd() % n;
ans.push_back(cur);
set<int> not_used;
for (int i = 0; i < n; i++) {
if (i != cur) not_used.insert(i);
}
auto try_find = [&](int v) {
vec<int> t(all(not_used));
if (!are_connected({v}, t)) return -1;
shuffle(all(t), rnd);
int tl = 0;
int tr = len(t) - 1;
auto get_part = [&](int f) {
vec<int> r;
for (int i = 0; i <= f; i++)
r.push_back(t[i]);
return r;
};
while (tl != tr) {
int tm = (tl + tr) / 2;
if (are_connected({v}, get_part(tm))) {
tr = tm;
} else {
tl = tm + 1;
}
}
return t[tl];
};
while (true) {
if (not_used.empty()) break;
int u = try_find(ans.back());
if (u == -1) break;
ans.push_back(u);
not_used.erase(u);
}
while (true) {
if (not_used.empty()) break;
int u = try_find(ans.front());
if (u == -1) break;
ans.push_front(u);
not_used.erase(u);
}
return vec<int>(all(ans));
};
int T = 15;
vec<int> best;
while (T--) {
auto g = attempt();
if (len(g) > len(best))
best = g;
if(len(best) == n) break;
}
return best;
}
}
