#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 260;
bool query(vector <int> a, vector <int> b){
/*for(auto x : a)
cout << x << ' ';
cout << '\n';
for(auto x : b)
cout << x << ' ';
cout << '\n';
cout << '\n';*/
if(a == b)
return false;
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{
reverse(c.begin(), c.end());
for(auto x : c)
a.push_back(x);
return a;
}
}
for(auto x : a){
if(are_connected({x}, c)){
for(auto y : c){
if(are_connected({x}, {y})){
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;
}
}
}
}
return a;
}
