#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector <int>;
using vll = vector <ll>;
const ll MAXN = 256;
vll adj[MAXN];
ll mat[MAXN][MAXN];
// diameter common fishel L
pair <ll, vi> bfs (ll n, ll u) {
vector <char> vis(n, false);
vll dis(n), from(n);
queue <ll> q;
vis[u] = true;
dis[u] = 0;
from[u] = u;
q.push(u);
ll far = u;
while (q.size()) {
ll u = q.front(); q.pop();
for (ll v : adj[u]) {
if (vis[v]) continue;
vis[v] = true;
dis[v] = dis[u]+1;
from[v] = u;
q.push(v);
far = v;
}
}
ll ffar = far;
vi path;
while (far != from[far]) {
path.push_back(far);
far = from[far];
}
path.push_back(far);
return { ffar, path };
}
vi longest_trip (int n, int d) {
fill(adj, adj+n, vll({}));
for (ll u = 0; u < n; u++) {
for (ll v = u+1; v < n; v++) {
if (are_connected(vi({ int(u) }), vi({ int(v) }))) {
adj[u].push_back(v);
adj[v].push_back(u);
mat[u][v] = true;
mat[v][u] = true;
} else {
mat[u][v] = false;
mat[v][u] = false;
}
}
}
vi ans = {};
for (ll u = 0; u < n; u++) {
vi path = bfs(n, bfs(n, 0).first).second;
if (path.size() > ans.size()) ans = path;
}
deque <int> dq;
for (ll i : ans) dq.push_back(i);
ll ex1 = dq.front(), ex2 = dq.back();
vector <char> vis(n, false);
for (ll u : dq) vis[u] = true;
for (ll k = 0; k < n; k++) {
for (ll u = 0; u < n; u++) {
if (vis[u]) continue;
vis[u] = true;
if (mat[u][ex1]) {
dq.push_front(u);
ex1 = u;
} else if (mat[u][ex2]) {
dq.push_back(u);
ex2 = u;
} else vis[u] = false;
}
}
ans = {};
for (ll i : dq) ans.push_back(i);
return ans;
}
