#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int N;
void find_longest(int i, vector<int> adj[], vector<int>& res) {
vector<int> p(N, -1), mx(N, -1);
vector<int> dist(N, -1);
queue<int> q;
q.push(i);
p[i] = -2;
dist[i] = 0;
while (q.size()) {
int layer = q.size();
vector<int> toadd;
while (layer--) {
int v = q.front();
q.pop();
for (auto& u : adj[v]) {
if (p[u] == -1) {
if (dist[u] < dist[v] + 1) {
dist[u] = dist[v] + 1;
mx[u] = v;
toadd.push_back(u);
}
}
}
}
for (auto& u : toadd) {
q.push(u);
p[u] = mx[u];
}
}
int j = i;
for (int k = 0; k < N; ++k) {
if (dist[k] > dist[j]) {
j = k;
}
}
vector<int> now{j};
vector<bool> vis(N);
vis[j] = 1;
while (true) {
bool ok = false;
for (auto& u : adj[now.back()]) {
if (!vis[u]) {
vis[u] = true;
now.push_back(u);
ok = true;
break;
}
}
if (!ok) break;
}
if (now.size() > res.size()) res = now;
}
std::vector<int> longest_trip(int _N, int D)
{
N = _N;
vector<int> adj[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);
}
}
}
// for (int i = 0; i < N; ++i) {
// cout << i << " : ";
// for (auto& u : adj[i]) {
// cout << u << " ";
// }
// cout << "\n";
// }
// cout << "\n";
vector<int> res;
for (int i = 0; i < N; ++i) {
find_longest(i, adj, res);
}
return res;
}
