#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define inf LLONG_MAX/2
#define ff first
#define ss second
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
#define last(s) (*--s.end())
#define first(s) (*s.begin())
vector<int> longest_trip(int n, int D)
{
bool adj[256][256];
FOR(i, n) FOR(j, n) adj[i][j] = 0;
FOR(i, n) FOR(j, i) {
if(are_connected({i}, {j})){
adj[i][j] = 1;
adj[j][i] = 1;
}
}
{ // 2 components
vector<int> vis(n);
vector<vector<int>> comp;
function<void(int)> dfs = [&](int a){
comp.back().push_back(a);
vis[a] = 1;
FOR(b, n) if(adj[a][b] && !vis[b]) dfs(b);
};
FOR(i, n){
if(!vis[i]) {
comp.push_back({});
dfs(i);
}
}
if(comp.size() == 2){
if(comp[0].size() < comp[1].size()) swap(comp[0], comp[1]);
return comp[0];
}
}
{ // full graph
bool full = 1;
FOR(i, n) if(accumulate(adj[i], adj[i] + n, 0) != n - 1) full = 0;
if(full) {
vector<int> r;
FOR(i, n) r.push_back(i);
return r;
}
}
bool vis[256];
FOR(i, 256) vis[i] = 0;
FOR(st, n){
int a = -1, b;
FOR(j, n) FOR(k, j){
if(adj[st][j] && adj[st][k] && !adj[j][k]) a = j, b = k;
}
if(a == -1) continue;
deque<int> res;
res.push_back(st);
res.push_back(a);
res.push_front(b);
vis[st] = 1; vis[a] = 1; vis[b] = 1;
FOR(_, n){
bool f = 0;
FOR(j, n){
if(vis[j]) continue;
if(adj[a][j] && !adj[b][j]){
f = 1;
a = j;
res.push_back(a);
vis[a] = 1;
}
else if(adj[b][j] && !adj[a][j]){
f = 1;
b = j;
res.push_front(b);
vis[b] = 1;
}
}
if(!f){
f = 0;
FOR(x, n){
if(vis[x]) continue;
FOR(y, x){
if(vis[y]) continue;
if(adj[a][x] && adj[b][y] && !adj[x][y]){
f = 1;
a = x;
b = y;
res.push_back(a);
vis[a] = 1;
res.push_front(b);
vis[b] = 1;
}
}
}
if(!f){
FOR(x, n) if(!vis[x]) res.push_back(x);
return vector<int>(all(res));
}
}
}
return vector<int>(all(res));
}
return {0};
}
