#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 260;
bool query(vector <int> a, vector <int> b){
if(a == b)
return true;
return are_connected(a, b);
}
vector<int> longest_trip(int n, int D){
queue <vector <int>> pq;
for(int i = 0;i < n;i++){
pq.push({i});
}
while(pq.size() > 2){
vector <int> a = pq.front();
pq.pop();
vector <int> b = pq.front();
pq.pop();
vector <int> c = pq.front();
pq.pop();
if(query({a.back()}, {b.back(), c.back()})){
if(!query({a.back()}, {b.back()})){
swap(b, c);
}
reverse(b.begin(), b.end());
for(auto x : b)
a.push_back(x);
pq.push(a);
pq.push(c);
}
else{
reverse(b.begin(), b.end());
for(auto x : b)
c.push_back(x);
pq.push(a);
pq.push(c);
}
}
vector <int> a = pq.front();
pq.pop();
vector <int> c = pq.front();
pq.pop();
if(!query(a, c)){
if(a.size() < c.size())
swap(a, c);
return a;
}
if(!query({c[0]}, {c.back()}))
swap(a, c);
if(!query({a[0]}, {a.back()})){
if(query({a[0]}, {c[0]})){
reverse(a.begin(), a.end());
for(auto x : c)
a.push_back(x);
return a;
}
else{
for(auto x : c)
a.push_back(x);
return a;
}
}
int l = 0, r = a.size();
r--;
while(l < r){
int mid = (l+r)/2;
vector <int> v;
for(int i = l;i <= mid;i++){
v.push_back(a[i]);
}
if(are_connected(v, c)){
r = mid;
}
else{
l = mid+1;
}
}
int x = a[l];
l = 0;
r = c.size();
r--;
while(l < r){
int mid = (l+r)/2;
vector <int> v;
for(int i = l;i <= mid;i++){
v.push_back(c[i]);
}
if(are_connected(v, {x})){
r = mid;
}
else{
l = mid+1;
}
}
int y = c[l];
while(a.back() != x){
int t = a[0];
reverse(a.begin(), a.end());
a.pop_back();
reverse(a.begin(), a.end());
a.push_back(t);
}
while(c.back() != y){
int t = c[0];
reverse(c.begin(), c.end());
c.pop_back();
reverse(c.begin(), c.end());
c.push_back(t);
}
reverse(c.begin(), c.end());
for(auto x : c)
a.push_back(x);
return a;
}
