#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int fp(int n, vector<int> &dsu) {
if (dsu[n] == n) return n;
return dsu[n] = fp(dsu[n], dsu);
}
std::vector<int> longest_trip(int N, int D)
{
vector<bool> vis(N, 0);
vector<int> dist(N, 0);
vector<int> pa(N);
vector<int> ans;
vector<int> dsu(N);
vector<vector<int>> adj(N);
for (int i = 0; i < N; i++) dsu[i] = i;
for (int i = 0; i + 1 < N; i++) {
for (int j = i + 1; j < N; j++) {
if (are_connected({i}, {j})) {
adj[i].emplace_back(j);
adj[j].emplace_back(i);
}
}
}
queue<int> q;
q.emplace(0);
vis[0] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto v : adj[u]) {
if (vis[v]) continue;
vis[v] = 1;
dist[v] = dist[u] + 1;
q.emplace(v);
}
}
int root = -1, mx = -1;
for (int i = 0; i < N; i++) {
if (mx < dist[i]) {
mx = dist[i];
root = i;
}
}
fill(dist.begin(), dist.end(), 0);
fill(vis.begin(), vis.end(), 0);
vis[root] = 1;
pa[root] = root;
q.emplace(root);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto v : adj[u]) {
if (vis[v]) continue;
vis[v] = 1;
dist[v] = dist[u] + 1;
pa[v] = u;
q.emplace(v);
}
}
int cur = -1;
mx = -1;
for (int i = 0; i < N; i++) {
if (mx < dist[i]) {
mx = dist[i];
cur = i;
}
}
while (cur != root) {
ans.push_back(cur);
cur = pa[cur];
}
return ans;
}
