#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;
vector<int> f(vector<int> vv, vector<vector<bool>> &edge){
vector<int> x(n + 5, 1);
for(int i = 0; i < vv.size(); i++){
for(int j = i + 1; j < vv.size(); j++){
if(edge[vv[i]][vv[j]]){
x[i]++;
x[j]++;
}
}
}
ll idx = 0,mn = vv.size();
for(int i = 0; i < vv.size(); i++){
if(mn > x[i]){
mn = x[i];
idx = i;
}
}
if(mn == vv.size()) return vv;
vector<int> vv1,vv2,vv3;
for(int i = 0; i < vv.size(); i++){
if(!edge[vv[i]][vv[idx]]) vv1.pb(vv[i]);
}
for(int i = 0; i < vv.size(); i++){
int ok = 0;
for(auto it : vv1){
if(edge[vv[i]][it]) ok = max(ok, 1);
if(it == vv[i]) ok = 2;
}
if(!ok) vv3.pb(vv[i]);
else if(ok == 1) vv2.pb(vv[i]);
}
// cout << "-> "; for(auto it : vv) cout << it << ' '; cout << endl;
// cout << "-> "; for(auto it : vv1) cout << it << ' '; cout << endl;
// cout << "-> "; for(auto it : vv2) cout << it << ' '; cout << endl;
// cout << "-> "; for(auto it : vv3) cout << it << ' '; cout << endl;
vector<int> ans = f(vv2, edge);
if(ans.empty()){
if(vv1.size() > vv3.size()) return vv1;
return vv3;
}
ll num = vv[idx];
vector<int> v;
for(auto it : vv3) if(it != num) v.pb(it);
v.pb(num);
for(auto it : ans) v.pb(it);
for(auto it : vv1) if(edge[it][v[v.size() - 1]]) num = it;
v.pb(num);
for(auto it : vv1) if(it != num) v.pb(it);
return v;
}
std::vector<int> longest_trip(int N, int D){
n = N;
vector<vector<bool>> edge(n + 5, vector<bool>(n + 5, false));
for(int i = 0; i < n; i++){
edge[i][i] = true;
for(int j = i + 1; j < n; j++){
if(!are_connected({i}, {j})) continue;
edge[i][j] = edge[j][i] = true;
}
}
vector<int> v;
for(int i = 0; i < n; i++) v.pb(i);
return f(v, edge);
}
