#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> res;
for(auto u : a) res.push_back(u);
return res;
}
