#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(time(0));
vector<int> longest_trip(int n, int d) {
auto Ask = [&](vector<int> a, vector<int> b) {
return are_connected(a, b);
};
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
shuffle(idx.begin(), idx.end(), rng);
vector<int> pa, pb;
pa.push_back(idx[0]);
pb.push_back(idx[1]);
bool know = false;
for (int ver = 2; ver < n; ver++) {
int i = idx[ver];
if (know) {
if (Ask({i}, {pa.back()})) {
pa.push_back(i);
know = false;
continue;
} else {
pb.push_back(i);
know = true;
continue;
}
}
if (Ask({i}, {pa.back()})) {
pa.push_back(i);
know = false;
continue;
}
if (Ask({i}, {pb.back()})) {
pb.push_back(i);
know = true;
continue;
}
while (!pb.empty()) {
pa.push_back(pb.back());
pb.pop_back();
}
pb.push_back(i);
know = false;
}
if (pa.empty()) {
return pb;
}
if (pb.empty()) {
return pa;
}
if (!Ask(pa, pb)) {
if ((int) pa.size() < (int) pb.size()) {
swap(pa, pb);
}
return pa;
}
vector<int> L, R;
L.push_back(pa[0]);
if ((int) pa.size() > 1) {
L.push_back(pa.back());
}
R.push_back(pb[0]);
if ((int) pb.size() > 1) {
R.push_back(pb.back());
}
if (Ask(L, R)) {
if (Ask({pa[0]}, {pb[0]})) {
reverse(pa.begin(), pa.end());
vector<int> res;
for (int i : pa) {
res.push_back(i);
}
for (int i : pb) {
res.push_back(i);
}
return res;
}
if (Ask({pa.back()}, {pb[0]})) {
vector<int> res;
for (int i : pa) {
res.push_back(i);
}
for (int i : pb) {
res.push_back(i);
}
return res;
}
if (Ask({pa[0]}, {pb.back()})) {
vector<int> res;
for (int i : pb) {
res.push_back(i);
}
for (int i : pa) {
res.push_back(i);
}
return res;
}
reverse(pa.begin(), pa.end());
vector<int> res;
for (int i : pb) {
res.push_back(i);
}
for (int i : pa) {
res.push_back(i);
}
return res;
}
int x = -1, y = -1;
{
int low = 0, high = (int) pa.size() - 1;
while (low <= high) {
int mid = (low + high) >> 1;
vector<int> qv;
for (int i = 0; i <= mid; i++) {
qv.push_back(pa[i]);
}
if (Ask(qv, pb)) {
x = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
}
{
int low = 0, high = (int) pb.size() - 1;
while (low <= high) {
int mid = (low + high) >> 1;
vector<int> qv;
for (int i = 0; i <= mid; i++) {
qv.push_back(pb[i]);
}
if (Ask({pa[x]}, qv)) {
y = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
}
int ca = (int) pa.size();
int cb = (int) pb.size();
vector<int> new_a;
for (int i = 0; i < ca; i++) {
new_a.push_back(pa[(i + 1 + x) % ca]);
}
pa = new_a;
vector<int> new_b;
for (int i = 0; i < cb; i++) {
new_b.push_back(pb[(i + 1 + y) % cb]);
}
pb = new_b;
reverse(pb.begin(), pb.end());
vector<int> res;
for (int i : pa) {
res.push_back(i);
}
for (int i : pb) {
res.push_back(i);
}
return res;
}
