#include "longesttrip.h"
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
vector<int> ADJ[257];
bool in_path[257];
int longest_length = 0;
int current_length = 0;
stack<int> path;
void dfs(int node, int parent) {
if (in_path[node]) return;
in_path[node] = true;
current_length++;
longest_length = max(longest_length, current_length);
for (int child : ADJ[node]) {
if (child == parent) continue;
dfs(child, node);
}
in_path[node] = false;
current_length--;
}
bool find_path(int node, int parent) {
if (in_path[node]) return false;
in_path[node] = true;
path.push(node);
current_length++;
if (current_length == longest_length) {
in_path[node] = false;
return true;
}
for (int child : ADJ[node]) {
if (child == parent) continue;
if (find_path(child, node)) {
in_path[node] = 0;
return true;
};
}
in_path[node] = false;
current_length--;
path.pop();
return 0;
}
vector<int> longest_trip(int N, int D)
{
if (D == 3) {
vector<int> ans;
for (int i = 0; i < N; i++) {
ans.push_back(i);
}
return ans;
}
for (int i = 0; i < N; i++) {
ADJ[i].clear();
}
longest_length = 0;
for (int i = 0; i < N-1; 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++) {
current_length = 0;
dfs(i, i);
}
for (int i = 0; i < N; i++) {
find_path(i, i);
}
vector<int> ans;
for (; !path.empty(); path.pop()) {
ans.push_back(path.top());
}
return ans;
}
