#include "longesttrip.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
bool con[305][305],was[305];
vector<int> res,cur;
void dfs(int x){
cur.pb(x);
was[x]=true;
if(cur.size()>res.size()) res=cur;
for(int y=1;y=300;y++){
if(!was[y]&&con[x][y]){
dfs(y);
}
}
cur.pop_back();
}
mt19937 mrand(time(0));
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){
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
con[i][j]=con[j][i]=are_connected({i},{j});
}
}
res={};
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) was[j]=false;
dfs(i);
}
return res;
}
vector<int> ord(n);
iota(ord.begin(),ord.end(),0);
shuffle(ord.begin(),ord.end(),mrand);
vector<int> chn1(1,ord.back()),chn2;
ord.pop_back();
for(int i:ord){
if(!chn1.empty()&&!chn2.empty()){
bool ok1=are_connected({i},chn1),ok2=are_connected({i},chn2);
if(ok1&&ok2){
if(are_connected({i},{chn2[0]})) swap(chn1,chn2);
swap(chn1[0],chn1.back());
int l=0,r=chn2.size()-1,p=0;
while(l<=r){
int mid=(l+r)/2;
vector<int> qv;
for(int j=0;j<=mid;j++) qv.pb(chn2[j]);
if(are_connected({i},qv)) p=mid,r=mid-1;
else l=mid+1;
}
swap(chn2[p],chn2[0]);
chn1.pb(i);
for(int v:chn2) chn1.pb(v);
chn2.clear();
continue;
}
if(!ok1) chn2.pb(i);
if(!ok2) chn1.pb(i);
continue;
}
bool ok=are_connected({i},chn1);
if(!ok){
chn2={i};
continue;
}
if(are_connected({i},{chn1[0]})){
reverse(chn1.begin(),chn1.end());
chn1.pb(i);
continue;
}
int l=0,r=(int)chn1.size()-1,p=0;
while(l<=r){
int mid=(l+r)/2;
vector<int> qv;
for(int j=mid;j<(int)chn1.size();j++) qv.pb(chn1[j]);
if(are_connected({i},qv)) p=mid,l=mid+1;
else r=mid-1;
}
p=chn1[p];
while(chn1.back()!=p){
int x=chn1.back();
chn1.pop_back();
reverse(chn1.begin(),chn1.end());
chn1.pb(x);
reverse(chn1.begin(),chn1.end());
}
chn1.pb(i);
}
return chn1.size()>chn2.size()?chn1:chn2;
}
