#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;
}
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.
pt2.push_back(i);
}
if(pt1.size()>pt2.size()){
return pt1;
}
return pt2;
}
