#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << "----> " << x << endl;
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")
std::vector<int> longest_trip(int N, int D){
int n = N;
vector<vector<int>> v(n + 5);
vector<vector<bool>> edge(n + 5, vector<bool>(n + 5, false));
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(!are_connected({i}, {j})) continue;
v[i].pb(j);
v[j].pb(i);
edge[i][j] = edge[j][i] = true;
}
}
vector<int> ans;
ans.pb(0);
ll l = 0,r = 0;
if(edge[0][1] and edge[0][2]){
ans.insert(ans.begin(), 1);
ans.pb(2);
l = 1;
r = 2;
}
else if(edge[0][1]){
ans.pb(1);
ans.pb(2);
r = 2;
}
else{
ans.pb(2);
ans.pb(1);
r = 1;
}
for(int i = 3; i < n; i++){
if(edge[i][r]){
ans.pb(i);
r = i;
}
else{
ans.insert(ans.begin(), i);
l = i;
}
}
return ans;
}
