#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 260;
int n;
int adj[maxn][maxn];
int qry(int u, int v) {
int ret = are_connected({u}, {v});
return adj[u][v] = adj[v][u] = ret;
}
vector<int> a, b;
vector<int> longest_trip(int N, int D) {
n = N;
for (int i=0;i<n;i++) for (int j=0;j<n;j++) adj[i][j] = -1;
a = {0}, b = {1};
for (int i=2;i<n;i++) {
int A = a.back(), B = b.back();
if (qry(A, i)) a.push_back(i);
else {
if (adj[A][B] == 0) b.push_back(i);
else if (adj[A][B] == -1) {
if (qry(B, i)) b.push_back(i);
else {
while (b.size()) {
a.push_back(b.back());
b.pop_back();
}
b.push_back(i);
}
}
}
}
// cout << "test\n";
// for (int i:a) cout << i << " "; cout << endl;
// for (int i:b) cout << i << " "; cout << endl;
if (a.size() < b.size()) swap(a, b);
if (b.size() == 0 || !are_connected(a, b)) return a;
int asz = a.size(), bsz = b.size();
int l = 0, r = asz - 1;
while (l < r) {
int mid = (l+r)/2;
vector<int> temp = {a.back()};
for (int i=0;i<mid;i++) temp.push_back(a[i]);
if (are_connected(temp, b)) r = mid;
else l = mid + 1;
}
int A = (l - 1 + asz) % asz;
l = 0, r = bsz - 1;
while (l < r) {
int mid = (l+r)/2;
vector<int> temp = {b.back()};
for (int i=0;i<l;i++) temp.push_back(b[i]);
if (are_connected(temp, {a[A]})) r = mid;
else l = mid + 1;
}
int B = (l - 1+ bsz) % bsz;
// cout << "Test " << A << " " << a[A] << " " << B << " " << b[B] << endl;
// for (int i:a) cout << i << " "; cout << endl;
// for (int i:b) cout << i << " "; cout << endl;
vector<int> ans;
if (A == 0) {
for (int i=asz-1;i>=0;i--) ans.push_back(a[i]);
} else {
for (int i=A+1;i<=A+asz;i++) ans.push_back(a[i % asz]);
}
if (B == bsz - 1) {
for (int i=bsz-1;i>=0;i--) ans.push_back(b[i]);
} else {
for (int i=B;i<B+bsz;i++) ans.push_back(b[i % bsz]);
}
return ans;
}
