#include "longesttrip.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
bool con[305][305];
vector<int> longest_trip(int n,int d){
if(d!=1) return {};
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});
}
}
vector<int> chn1(1,0),chn2;
for(int i=1;i<n;i++){
if(!chn1.empty()&&!chn2.empty()){
bool ok1=false,ok2=false;
for(int v:chn1) ok1=(ok1|con[v][i]);
for(int v:chn2) ok2=(ok2|con[v][i]);
if(ok1&&ok2){
for(int x=0;x<(int)chn1.size();x++){
if(con[chn1[x]][i]){
swap(chn1[x],chn1.back());
break;
}
}
for(int x=0;x<(int)chn2.size();x++){
if(con[chn2[x]][i]){
swap(chn2[x],chn2[0]);
break;
}
}
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=false;
for(int v:chn1) if(con[i][v]) ok=true;
if(!ok){
chn2={i};
continue;
}
if(con[chn1[0]][i]){
reverse(chn1.begin(),chn1.end());
chn1.pb(i);
continue;
}
while(!con[chn1.back()][i]){
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;
}
