#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int n, int D) {
if(D==3){
vector<int>ans(n);
iota(ans.begin(),ans.end(),0);
return ans;
}
if(D==2){
set<int>lef;
for(int i = 0;i<n;i++){
lef.insert(i);
}
vector<int>ans;
ans.push_back(0);
lef.erase(0);
while(lef.size()>1){
if(are_connected({ans.back()},{*lef.begin()})){
ans.push_back(*lef.begin());
lef.erase(lef.begin());
}
else{
ans.push_back(*(++lef.begin()));
lef.erase(++lef.begin());
}
}
if(are_connected({*lef.begin()},{ans.back()})){
ans.push_back(*lef.begin());
return ans;
}
ans.insert(ans.begin(),*lef.begin());
return ans;
}
assert(D==1);
bool adj[n][n];
for(int i = 0;i<n;i++){
fill(adj[i],adj[i]+n,0);
}
for(int i = 0;i<n;i++){
for(int j = i+1;j<n;j++){
if(are_connected({i},{j})){
adj[i][j]=adj[j][i]=1;
}
}
}
vector<int>pt1,pt2;
pt1.push_back(0);
for(int i = 1;i<n;i++){
int prev1 = pt1.back();
if(adj[prev1][i]){
pt1.push_back(i);
continue;
}
//not adjacent.
if(pt2.size()){
int prev2 = pt2.back();
if(adj[prev2][i]){
pt2.push_back(i);
}
else{
assert(adj[prev1][prev2]);
reverse(pt2.begin(),pt2.end());
pt1.insert(pt1.end(),pt2.begin(),pt2.end());
pt2.clear();
i--;
continue;
}
}
else{
pt2.push_back(i);
}
}
int mxi, mxj;
mxi=-1;
mxj=-1;
for(int i = 0;i<pt1.size();i++){
for(int j = 0;j<pt2.size();j++){
if(adj[pt1[i]][pt2[j]]){
if(mxi==-1){
mxi=i;
mxj=j;
continue;
}
int ollen = max(mxi+1,(int)pt1.size()-mxi)+max(mxj+1,(int)pt2.size()-mxj);
int newlen = max(i+1,(int)pt1.size()-i)+max(j+1,(int)pt2.size()-j);
if(newlen>ollen){
mxi=i;
mxj=j;
}
}
}
}
if(mxi==-1){
if(pt1.size()>pt2.size()){
return pt1;
}
return pt2;
}
vector<int>ans;
if(mxi+1>pt1.size()-mxi){
for(int i = 0;i<=mxi;i++){
ans.push_back(pt1[i]);
}
}
else{
for(int i = pt1.size()-1;i>=mxi;i--){
ans.push_back(pt1[i]);
}
}
if(mxj+1>pt2.size()-mxj){
for(int i = 0;i<=mxj;i++){
ans.push_back(pt2[i]);
}
}
else{
for(int i = pt2.size()-1;i>=mxj;i--){
ans.push_back(pt2[i]);
}
}
return ans;
}
