#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
typedef long long ll;
vector<vector<ll>> adj;
vector<ll> dist;
vector<bool> vst;
ll numVst;
void dfs1(ll cur, ll depth) {
dist[cur] = depth;
vst[cur] = true;
numVst++;
for (auto &e : adj[cur]) {
if (!vst[e]) dfs1(e, depth+1);
}
}
void dfs2(ll cur, ll depth) {
dist[cur] = depth;
vst[cur] = true;
for (auto &e : adj[cur]) {
if (!vst[e]) dfs2(e, depth+1);
}
}
vector<int> longest_trip(int n, int d) {
adj = vector<vector<ll>>(n);
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (are_connected({i}, {j})) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
dist = vector<ll>(n);
vst = vector<bool>(n);
numVst = 0;
dfs1(0, 0);
ll start = 0;
if (numVst <= n/2) {
for (int i = 0; i < n; i++) {
if (!vst[i]) {
start = i;
break;
}
}
}
else {
ll mx = 0;
for (int i = 0; i < n; i++) {
if (dist[i] > mx) {
start = i;
mx = dist[i];
}
}
}
dist = vector<ll>(n);
vst = vector<bool>(n);
dfs2(start, 0);
ll cur = 0;
ll mx = 0;
for (int i = 0; i < n; i++) {
if (dist[i] > mx) {
cur = i;
mx = dist[i];
}
}
vector<int> res = {(int)cur};
while (dist[cur]) {
for (auto &e : adj[cur]) {
if (dist[e] == dist[cur]-1) {
cur = e;
res.push_back(e);
break;
}
}
}
return res;
}
