#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
map<vector<int>, map<vector<int>, int> > mmm;
int query(vector<int> a, vector<int> b){
if (b.size()==2&&b.back()==b[b.size()-2])b.pop_back();
if (!mmm[a][b]&&!mmm[b][a])mmm[b][a]=mmm[a][b]=are_connected(a, b)+1;
return mmm[a][b]-1;
}
int queryd(deque<int> aa, deque<int> bb){
vector<int> a, b;
for (auto c:aa)a.pb(c);
for (auto c:bb)b.pb(c);
if (b.size()==2&&b.back()==b[b.size()-2])b.pop_back();
if (!mmm[a][b]&&!mmm[b][a])mmm[b][a]=mmm[a][b]=are_connected(a, b)+1;
return mmm[a][b]-1;
}
vector<int> longest_trip(int n, int d){
mmm.clear();
if (d==3){
vector<int> ans;
for (int i=0; i<n; ++i)ans.pb(i);
return ans;
}
if (d==2){
deque<int> ans(1, 0);
int done=1;
if (are_connected({0}, {1}))ans.pb(1);
else ans.pb(2), done=2;
for (int i=1; i<n; ++i)if (i!=done){
if (are_connected({i}, {ans.back()}))ans.pb(i);
else ans.push_front(i);
}
vector<int> res;
for (auto a:ans)res.pb(a);
return res;
}
vector<int> ord;
for (int i=0; i<n; ++i)ord.pb(i);
mt19937 rng(67);
shuffle(ord.begin(), ord.end(), rng);
deque<int> a(1, ord[0]), b(1, ord[1]);
bool prevb=0;
for (int j=2; j<n; ++j){
int i=ord[j];
if (!prevb){
if (query({i}, {a.back()}))a.pb(i), prevb=0;
else if (query({i}, {b.back()}))b.pb(i), prevb=1;
else{
prevb=0;
if (j+1<n){
if (query({i}, {ord[j+1]})){
while (b.size())a.pb(b.back()), b.pop_back();
b.pb(i);
b.pb(ord[j+1]);
}
else{
a.pb(ord[j+1]);
while (b.size())a.pb(b.back()), b.pop_back();
b.pb(i);
}
++j;
}
else{
while (b.size())a.pb(b.back()), b.pop_back();
b.pb(i);
}
}
}
else{
if (query({i}, {a.back()}))a.pb(i), prevb=0;
else b.pb(i), prevb=1;
}
}
if (b.size()>a.size())swap(a, b);
if (!queryd(a, b)){
vector<int> res;
for (auto c:a)res.pb(c);
return res;
}
if (!query({a[0], a.back()}, {b[0], b.back()})){
int low=-1, high=a.size()-1;
while (low+1<high){
int mid=(low+high)/2;
deque<int> temp;
for (int i=low+1; i<=mid; ++i)temp.pb(a[i]);
if (queryd(temp, b))high=mid;
else low=mid;
}
int froma=high;
low=-1, high=b.size()-1;
while (low+1<high){
int mid=(low+high)/2;
vector<int> temp;
for (int i=low+1; i<=mid; ++i)temp.pb(b[i]);
if (query({a[froma]}, temp))high=mid;
else low=mid;
}
vector<int> res;
for (int p=0; p<a.size(); ++p)res.pb(a[(p+froma+1)%a.size()]);
for (int p=0; p<b.size(); ++p)res.pb(b[(p+high)%b.size()]);
return res;
}
if (query({a.back()}, {b.back()})){
while (b.size())a.pb(b.back()), b.pop_back();
}
else if (query({a.back()}, {b[0]})){
for (auto c:b)a.pb(c);
}
else if (query({a[0]}, {b.back()})){
while (b.size())a.push_front(b.back()), b.pop_back();
}
else if (query({a[0]}, {b[0]})){
for (auto c:b)a.push_front(c);
}
vector<int> res;
for (auto c:a)res.pb(c);
return res;
}
