#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 300;
int n;
int dist[maxn];
int e[maxn][maxn];
queue <int> q;
int bfs(int poc){
q.push(poc);
memset(dist, -1, sizeof dist);
dist[poc] = 0;
while(!q.empty()){
int x = q.front();
q.pop();
for(int x2 = 0; x2 < n; x2++){
if(x2 == x || !e[x][x2] || dist[x2] != -1) continue;
dist[x2] = dist[x] + 1;
q.push(x2);
}
}
int naj = 0;
for(int i = 0; i < n; i++){
if(dist[i] > dist[naj]){
naj = i;
}
}
return naj;
}
vector<int> longest_trip(int N, int d){
n = N;
for(int i = 0; i < n; i++){
for(int j = i + 1; i < n; i++){
e[i][j] = e[j][i] = are_connected({i}, {j});
}
}
vector <int> v;
int x = bfs(bfs(0));
v.push_back(x);
while(dist[x] > 0){
for(int x2 = 0; x2 < n; x2++){
if(e[x2][x] && dist[x2] + 1 == dist[x]){
x = x2;
break;
}
}
v.push_back(x);
}
for(int i = 0; i < n; i++){
if(dist[i] == -1){
x = bfs(bfs(i));
break;
}
}
if(dist[x] + 1 > v.size()){
v.clear();
v.push_back(x);
while(dist[x] > 0){
for(int x2 = 0; x2 < n; x2++){
if(e[x2][x] && dist[x2] + 1 == dist[x]){
x = x2;
break;
}
}
v.push_back(x);
}
}
return v;
}
