#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
vector<vector<int>> neigh;
vector<bool> visited;
vector<int> longest_path(int i){
if(visited[i]) return {};
visited[i]=true;
vector<int> longest_vector;
for (int c : neigh[i])
{
vector<int> c_longest=longest_path(c);
if(c_longest.size()>longest_vector.size()) longest_vector=c_longest;
}
longest_vector.push_back(i);
return longest_vector;
}
std::vector<int> longest_trip(int N, int D)
{
vector<int> ret;
neigh.clear();
neigh.resize(N);
for (int i = 0; i < N-1; i++){
for (int j = i+1; j < N; j++)
{
if(are_connected({i}, {j})){
neigh[i].push_back(j);
neigh[j].push_back(i);
}
}
}
vector<int> longest_vector;
for (int i = 0; i < N; i++){
visited.clear();
visited.resize(N);
vector<int> c_longest=longest_path(i);
if(c_longest.size()>longest_vector.size()) longest_vector=c_longest;
}
return longest_vector;
}
