#include <vector>
#include <algorithm>
using namespace std;
// Provided by the grader
extern bool are_connected(vector<int> A, vector<int> B);
const int MAXN = 256;
vector<int> adj[MAXN];
vector<int> best_path;
void dfs(int node, vector<bool>& visited, vector<int>& path) {
visited[node] = true;
path.push_back(node);
if (path.size() > best_path.size()) {
best_path = path;
}
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
dfs(neighbor, visited, path);
}
}
path.pop_back();
visited[node] = false;
}
vector<int> longest_trip(int N, int D) {
// Clear previous data
for (int i = 0; i < N; ++i) {
adj[i].clear();
}
best_path.clear();
// Build the adjacency list
for (int i = 0; i < N; ++i) {
vector<int> candidates;
for (int j = i + 1; j < N; ++j) {
candidates.push_back(j);
}
if (candidates.empty()) continue;
if (are_connected({i}, candidates)) {
// Binary search to find exact connected nodes
for (int j : candidates) {
if (are_connected({i}, {j})) {
adj[i].push_back(j);
adj[j].push_back(i); // bidirectional
}
}
}
}
// Run DFS from each node
vector<bool> visited(N, false);
vector<int> path;
for (int i = 0; i < N; ++i) {
dfs(i, visited, path);
}
return best_path;
}
