#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")
int n;
void dfs(ll at, vector<vector<bool>> &edge, vector<int> &ans, vector<bool> &vis){
ans.pb(at);
vis[at] = true;
for(int i = 0; i < n; i++){
if(at == i or !edge[at][i] or vis[i]) continue;
dfs(i, edge, ans, vis);
}
}
std::vector<int> longest_trip(int N, int D){
n = N;
assert(0);
vector<vector<bool>> edge(n + 5, vector<bool>(n + 5, false));
vector<int> v(n + 5, 0LL);
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(!are_connected({i}, {j})) continue;
v[i]++;
v[j]++;
edge[i][j] = edge[j][i] = true;
}
}
vector<int> ans;
ll sz = (n + 1) / 2;
for(int i = 0; i < n; i++){
if(v[i] < sz){
for(int j = 0; j < n; j++){
if(i == j or edge[i][j]) continue;
ans.pb(j);
}
return ans;
}
}
vector<bool> vis(n + 5, false);
dfs(0, edge, ans, vis);
assert(ans.size() >= sz);
return ans;
}
