#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
template<typename T>
int len(T &a){return a.size();}
int ask(int a, int b){
return are_connected({a}, {b});
}
vector<int> longest_trip(int n, int d)
{
if(d >= 2){
deque<int> cur = {0};
vector<int> done(n, 0);
done[0] = 1;
for(int i = 1; i < n; i ++){
if(ask(cur[0], i)){
cur.push_back(i);
done[i] = 1;
break;
}
}
for(int i = 0; i < n; i ++){
if(done[i]) continue;
if(ask(cur[0], i)){
cur.push_front(i);
}else cur.push_back(i);
}
vector<int> res;
for(auto u : cur) res.push_back(u);
return res;
}
deque<int> a = {0}, b = {1};
for(int i = 2; i < n; i ++){
if(ask(a.back(), i)){
a.push_back(i);
}else if(ask(b.back(), i)){
b.push_back(i);
}else{
for(int i = len(b) - 1; i >= 0; i --) a.push_back(b[i]);
b = {i};
}
}
if(len(b) > len(a)) swap(a, b);
vector<int> aa, bb;
for(auto u : a) aa.push_back(u);
for(auto u : b) bb.push_back(u);
if(are_connected(aa, bb) == 0){
if(len(aa) > len(bb)) return aa;
return bb;
}
vector<int> res;
if(ask(a[0], b[0])){
for(int i = len(a) - 1; i >= 0; i --){
res.push_back(a[i]);
}
for(int i = 0; i < len(b); i ++) res.push_back(b[i]);
return res;
}
if(ask(a[0], b.back())){
for(auto u : b) res.push_back(u);
for(int i = 0; i < len(a); i ++) res.push_back(a[i]);
return res;
}
if(ask(a.back(), b[0])){
for(auto u : a) res.push_back(u);
for(auto u : b) res.push_back(u);
return res;
}
if(ask(a.back(), b.back())){
for(auto u : a) res.push_back(u);
for(int i = len(b) - 1; i >= 0; i --) res.push_back(b[i]);
return res;
}
assert(0);
int i = 0, j = 0;
while(are_connected({aa[i]}, bb) == 0){
i ++;
}
while(ask(aa[i], bb[j]) == 0) j ++;
for(int k = i + 1; k < len(aa); k ++) res.push_back(aa[k]);
for(int k = 0; k <= i; k ++) res.push_back(aa[k]);
for(int k = j; k < len(bb); k ++) res.push_back(aa[k]);
for(int k = 0; k < j; k ++) res.push_back(bb[k]);
return res;
}
