#include "longesttrip.h"
#ifdef ngu
#include "grader.cpp"
#endif // ngu
#include<bits/stdc++.h>
using namespace std;
pair<int, int> Find (vector<int> a, vector<int> b) {
if (!are_connected(a, b)) return make_pair(-1, -1);
int l = 0, r = a.size() - 1, lastx = -1, lasty = -1;
while (l <= r) {
int mid = l + r >> 1;
vector<int> ask;
for(int i = 0; i <= mid; i++) ask.push_back(a[i]);
if (are_connected(ask, b)) {
lastx = mid;
r = mid - 1;
} else l = mid + 1;
}
l = 0, r = b.size() - 1;
while (l <= r) {
int mid = l + r >> 1;
vector<int> ask;
for(int i = 0; i <= mid; i++) ask.push_back(b[i]);
if (are_connected(ask, {a[lastx]})) {
lasty = mid;
r = mid - 1;
} else l = mid + 1;
}
assert(are_connected({a[lastx]}, {b[lasty]}));
return make_pair(lastx, lasty);
}
vector<int> rev (vector<int> a) {
reverse(a.begin(), a.end());
return a;
}
vector<int> sum (vector<int> a, vector<int> b) {
for(int &j : b) a.push_back(j);
return a;
}
std::vector<int> longest_trip(int n, int d)
{
vector<int> a, b;
a.push_back(0);
b.push_back(1);
for(int i = 2; i < n; i++) {
if (are_connected({a.back()}, {i})) a.push_back(i);
else if (are_connected({b.back()}, {i})) b.push_back(i);
else {
reverse(b.begin(), b.end());
for(int &j : b) a.push_back(j);
b = {i};
}
}
if (a.size() > b.size()) swap(a, b);
if (a.size() > 2 && !are_connected({a[0]}, {a.back()})) {
if (are_connected({a[0]}, {b[0]})) return sum(rev(a), b);
else return sum(a, b);
}
if (b.size() > 2 && !are_connected({b[0]}, {b.back()})) {
if (are_connected({a[0]}, {b[0]})) return sum(rev(a), b);
else return sum(b, a);
}
auto [x, y] = Find(a, b);
if (x < 0) return b;
vector<int> ans;
for(int j = x + 1; j < a.size(); j++) ans.push_back(a[j]);
for(int j = 0; j <= x; j++) ans.push_back(a[j]);
for(int j = y; j < b.size(); j++) ans.push_back(b[j]);
for(int j = 0; j < y; j++) ans.push_back(b[j]);
return ans;
}
