#include "longesttrip.h"
#define sz(v) (int) v.size()
#define ff first
#define ss second
using namespace std;
typedef pair<int,int> ii;
vector<int> longest_trip(int N, int D)
{
vector<vector<bool>> A(N);
for(int i = 0; i < N; ++i) A[i].resize(N);
for(int i = 0; i < N; ++i){
for(int j = 0; j < i; ++j){
A[i][j] = are_connected({i},{j});
A[j][i] = A[i][j];
}
}
vector<int> G(N);
for(int i = 0; i < N; ++i){
for(int j = 0; j < N; ++j) if(A[i][j]) G[i]++;
}
int x = 0;
for(int i = 1; i < N; ++i){
if(G[i] < G[x]) x = i;
}
vector<int> ans;
if(G[x] <= (N/2)-1){
for(int i = 0; i < N; ++i){
if((i == x) || A[x][i]) continue;
ans.push_back(i);
}
return ans;
}
// G[x] >= (N/2) -> G[i] >= (N/2) for all 0 <= i < N
vector<bool> T(N,false);
ans = {0};
T[0] = 1;
int last = 0;
for(int i = 1; i < (N+1)/2; ++i){
for(int j = 0; j < N; ++j){
if(T[j] || !A[last][j] || (j == last)) continue;
// j is not in ans, j is adjacent to last, j is not last
ans.push_back(j);
last = j;
T[j] = 1;
break;
}
}
return ans;
}
