#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 (!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){
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;
}
mmm.clear();
vector<int> ord;
for (int i=0; i<n; ++i)ord.pb(i);
mt19937 gen(67);
shuffle(ord.begin(), ord.end(), gen);
deque<int> ans(1, ord[0]);
set<int> s;
for (int i=1; i<n; ++i)s.insert(i);
int loop=40000;
while (loop--&&s.size()>n/2){
vector<int> temp;
for (int a:s){
int i=ord[a];
if (query({i}, {ans.back()})){
ans.pb(i);
temp.pb(a);
continue;
}
if (query({i}, {ans[0]})){
ans.push_front(i);
temp.pb(a);
continue;
}
if (ans.size()>=4){
ans.insert(ans.begin()+2, i);
temp.pb(a);
continue;
}
for (int j=1; j<ans.size(); ++j)if (query({i}, {ans[j-1]})&&query({i}, {ans[j]})){
ans.insert(ans.begin()+j, i);
temp.pb(a);
break;
}
}
for (auto a:temp)s.erase(a);
}
vector<int> res;
for (auto a:ans)res.pb(a);
return res;
}
